#include #include #include #include #include #define repeat(i, n) for (int i = 0; (i) < (n); ++(i)) #define whole(f, x, ...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ##__VA_ARGS__); })(x) typedef long long ll; using namespace std; template void setmax(T &a, T const &b) { if (a < b) a = b; } const ll inf = ll(1e18) + 9; int main() { int n, m; cin >> n >> m; vector u(n); repeat(i, n) cin >> u[i]; vector>> g(n); repeat(i, n - 1) { int a, b, c; cin >> a >> b >> c; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } function(int, int)> dfs = [&](int i, int p) { vector cur(m / 2 + 1, -inf); cur[0] = u[i]; for (auto it : g[i]) { int j, c; tie(j, c) = it; if (j == p) continue; vector nxt(m / 2 + 1, -inf); vector prv = dfs(j, i); repeat(x, m / 2 + 1) { setmax(nxt[x], cur[x]); repeat(y, m / 2 + 1) { if (x + y + c >= m / 2 + 1) break; setmax(nxt[x + y + c], cur[x] + prv[y]); } } cur.swap(nxt); } return cur; }; vector dp = dfs(0, -1); cout << *whole(max_element, dp) << endl; }