Example

Input

3 2
1 2 1
2 3 2
1 10 100


Output

320
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n,m;
  cin>>n>>m;
  using P = pair<Int, Int>;
  vector<vector<P> > G(n);
  for(Int i=0;i<n-1;i++){
    Int u,v,c;
    cin>>u>>v>>c;
    u--;v--;
    G[u].emplace_back(v,c);
    G[v].emplace_back(u,c);
  }
  vector<Int> w(n);
  for(Int i=0;i<n;i++) cin>>w[i];
  priority_queue<Int> pq;
  vector<Int> dp(n);
  function<void(Int, Int, Int)> dfs=[&](Int r,Int v,Int p){
    for(auto e:G[v]){
      Int u=e.first;
      if(u==p) continue;
      dfs(r,u,v); 
    }
    Int idx=-1;
    for(auto e:G[v]){
      Int u=e.first,c=e.second;
      if(u==p) continue;
      if(idx<0||dp[u]+c>dp[v])
	idx=u,dp[v]=dp[u]+c;
    }
    if(idx<0){
      dp[v]=0;
      return;
    }
    for(auto e:G[v]){
      Int u=e.first,c=e.second;
      if(u==p) continue;
      if(u==idx) continue;
      pq.emplace((dp[u]+c)*w[r]);
    }
    if(v==r) pq.emplace(dp[v]*w[r]);
  };
  
  for(Int i=0;i<n;i++) dfs(i,i,-1);
  
  Int ans=0;
  while(m&&!pq.empty()){
    ans+=pq.top();pq.pop();
    m--;
  }
  cout<<ans<<endl;
  return 0;
}