INF = 1 << 30 n,m = gets.split.map(&:to_i) T = n.times.map { gets.to_i } E = (n-1).times.map { gets.split.map(&:to_i) } O = Array.new(n).tap do |used| g = Array.new(n) { [] } E.each do |a,b,c| g[a] << b g[b] << a end index = 0 stack = [0] until stack.empty? v = stack.pop used[v] = index g[v].each do |to| if !used[to] stack << to end end index += 1 end end G = Array.new(n) { Array.new(n, INF) }.tap do |d| n.times do |i| d[i][i] = 0 end E.each do |a,b,c| d[a][b] = d[b][a] = c end n.times do |i| n.times do |j| n.times do |k| if d[i][j] > d[i][k] + d[k][j] d[j][i] = d[i][j] = d[i][k] + d[k][j] end end end end end dp = Array.new(n) { Array.new(m + 1) }.tap do |dp| dp[0][0] = T[0] (1 ... n).each do |i| dp[i][G[0][i]] = T[i] + T[0] end (1 .. m).each do |t| (1 ... n).each do |i| if dp[i][t] n.times.select {|v| O[v] > O[i]}.each do |j| if t + G[i][j] <= m dp[j][t + G[i][j]] = [dp[j][t + G[i][j]] ||= 0, dp[i][t] + T[j] ].max end end unless i == 0 if t + G[i][0] <= m dp[0][t + G[i][0]] = [ dp[0][t + G[i][0]] ||= 0, dp[i][t] ].max end end end end end end puts dp[0].compact.max