#include #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; vector> e[203]; int n, m; lli u[206]; vector sub(int cur, int par) { vector> v; cout << cur << endl; for (auto to : e[cur]) { if (to.first == par) continue; auto vv = sub(to.first, cur); vector hoge(m + 1, 0); rep(i, m+1) { if (i + 2 * to.second > m) { break; } hoge[i + 2 * to.second] = vv[i]; } v.push_back(hoge); } vector dp[2]; rep(i, 2) dp[i].assign(m + 1, u[cur]); rep(i, v.size()) { rep(j, m + 1) { rep(k, m + 1) { if (j + k > m) { break; } dp[(i + 1) % 2][j + k] = max(dp[(i + 1) % 2][j + k], dp[i%2][j] + v[i][k]); } } dp[i % 2].assign(m + 1, 0); } return dp[v.size() & 1]; } int main() { cin >> n >> m; rep(i, n) cin >> u[i]; int a, b, c; rep(i, n - 1) { cin >> a >> b >> c; e[a].push_back(make_pair(b, c)); e[b].push_back(make_pair(a, c)); } cout << sub(0, -1)[m] << endl; }