Example

Input

3 2
1 2 1
2 3 2
1 10 100


Output

320
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<vector<pair<int,ll> > > g;
vector<ll> cost;
vector<ll>res;

ll bfs(int a,int p,int b){
    //cerr << a << " " << p << " " << b << endl;
    if(a==b){
        for(auto x:g[a]){
            res.push_back(cost[b]*(x.second+bfs(x.first,a,b)));
        }
        return 0;
    }else{
        vector<ll>res2;
        for(auto x:g[a]){
            if(x.first!=p)res2.push_back(cost[b]*(x.second+bfs(x.first,a,b)));
        }
        if(res2.size()==0)return 0;
        sort(res2.begin(),res2.end());
        for(int i=0;i<res2.size()-1;i++){
            res.push_back(res2[i]);
        }
        return res2[res2.size()-1]/cost[b];
    }
}


int main(){
    int n,m;
    cin >> n >> m;
    g.resize(n);
    for(int i=0;i<n-1;i++){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--;
        b--;
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
    }
    cost.resize(n);
    for(int i=0;i<n;i++){
        cin >> cost[i];
    }
    for(int i=0;i<n;i++){
        bfs(i,-1,i);
    }
    ll ans = 0;
    if(m>=res.size()){
        for(auto x:res){
            ans += x;
        }
    }else{
        sort(res.rbegin(),res.rend());
        for(int i=0;i<m;i++){
            ans += res[i];
        }
    }
    cout << ans << endl;
    return 0;
}
