import std.algorithm; import std.array; import std.ascii; import std.container; import std.conv; import std.math; import std.numeric; import std.range; import std.stdio; import std.string; import std.typecons; void log(A...)(A arg) { stderr.writeln(arg); } int size(T)(in T s) { return cast(int)s.length; } struct Edge { int from, to, cost; } void main() { int N, M; readf("%s %s\n", &N, &M); auto U = new int[N]; foreach (i; 0 .. N) { U[i] = readln.chomp.to!int; } auto G = new Edge[][N]; auto D = new int[][](N, N); foreach (i; 0 .. N) foreach (j; 0 .. N) D[i][j] = int.max / 4; foreach (i; 0 .. N - 1) { int s, t, c; readf("%s %s %s\n", &s, &t, &c); G[s] ~= Edge(s, t, c); G[t] ~= Edge(t, s, c); D[s][t] = D[t][s] = c; } auto Vi = new int[N]; auto Vp = new int[N]; void dfs(int p, int v, ref int i) { //log([p, v, i]); Vi[i] = v; Vp[i] = p; i++; foreach (e; G[v]) { if (e.to == p) continue; dfs(v, e.to, i); } } int _ = 0; dfs(-1, 0, _); //log("Vi: ", Vi); //log("Vp: ", Vp); auto dp = new int[][][](2, N + 1, M + 1); foreach (i; 0 .. 2) foreach (j; 0 .. N + 1) dp[i][j][] = int.min / 4; foreach (j; 0 .. M + 1) dp[0][0][j] = U[0]; for (int i = 1; i < N; i++) { for (int t = 0; t <= M; t++) { int p = Vp[i]; int d = D[Vi[i]][p]; if (t - 1 >= 0) dp[i % 2][Vi[i]][t] = max(dp[i % 2][Vi[i]][t], dp[i % 2][Vi[i]][t - 1]); if (t - 2 * d >= 0) dp[i % 2][Vi[i]][t] = dp[(i - 1) % 2][p][t - 2 * d] + U[Vi[i]]; for (int j = 0; j < i; j++) { dp[i % 2][Vi[j]][t] = max(dp[i % 2][Vi[j]][t], dp[(i - 1) % 2][Vi[j]][t]); if (t - 1 >= 0) dp[i % 2][Vi[j]][t] = max(dp[i % 2][Vi[j]][t], dp[i % 2][Vi[j]][t - 1]); if (t - 2 * d >= 0) dp[i % 2][Vi[j]][t] = max(dp[i % 2][Vi[j]][t], dp[(i - 1) % 2][Vi[j]][t - 2 * d] + U[Vi[i]]); } } } writeln(dp[(N - 1) % 2][0][M]); }