Example

Input

3 2
1 2 1
2 3 2
1 10 100


Output

320
#include <iostream>
#include <vector>
#include <algorithm>
#define llint long long

using namespace std;

struct edge{
	llint to, cost;
	edge(){}
	edge(llint a, llint b){
		to = a, cost = b;
	}
};

llint n, m;
vector<edge> G[2005];
llint s[2005];
vector<llint> vec;

llint dfs(llint v, llint pre, llint r)
{	
	vector<llint> tmp;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i].to == pre) continue;
		llint res = dfs(G[v][i].to, v, r);
		tmp.push_back(res + G[v][i].cost);
	}
	sort(tmp.begin(), tmp.end());
	for(int i = 0; i < (int)tmp.size()-1; i++) vec.push_back(s[r] * tmp[i]);
	if(tmp.size()) return tmp.back();
	else return 0;
}

int main(void)
{
	cin >> n >> m;
	llint a, b, c;
	for(int i = 0; i < n-1; i++){
		cin >> a >> b >> c;
		G[a].push_back(edge(b, c));
		G[b].push_back(edge(a, c));
	}
	for(int i = 1; i <= n; i++) cin >> s[i];
	
	for(int i = 1; i <= n; i++) vec.push_back(s[i] * dfs(i, -1, i));
	sort(vec.rbegin(), vec.rend());
	
	llint ans = 0;
	for(int i = 0; i < min(m, (llint)vec.size()); i++) ans += vec[i];
	cout << ans << endl;
	
	return 0;
}
