Snuke Festival 2017 will be held in a tree with N vertices numbered 1,2, ...,N. The i-th edge connects Vertex a_i and b_i, and has joyfulness c_i.

The staff is Snuke and N-1 black cats. Snuke will set up the headquarters in some vertex, and from there he will deploy a cat to each of the other N-1 vertices.

For each vertex, calculate the niceness when the headquarters are set up in that vertex. The niceness when the headquarters are set up in Vertex i is calculated as follows:

* Let X=0.
* For each integer j between 1 and N (inclusive) except i, do the following:
* Add c to X, where c is the smallest joyfulness of an edge on the path from Vertex i to Vertex j.
* The niceness is the final value of X.

Constraints

* 1 \leq N \leq 10^{5}
* 1 \leq a_i,b_i \leq N
* 1 \leq c_i \leq 10^{9}
* The given graph is a tree.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}


Output

Print N lines. The i-th line must contain the niceness when the headquarters are set up in Vertex i.

Examples

Input

3
1 2 10
2 3 20


Output

20
30
30


Input

15
6 3 2
13 3 1
1 13 2
7 1 2
8 1 1
2 8 2
2 12 2
5 2 2
2 11 2
10 2 2
10 9 1
9 14 2
4 14 1
11 15 2


Output

16
20
15
14
20
15
16
20
15
20
20
20
16
15
20


Input

19
19 14 48
11 19 23
17 14 30
7 11 15
2 19 15
2 18 21
19 10 43
12 11 25
3 11 4
5 19 50
4 11 19
9 12 29
14 13 3
14 6 12
14 15 14
5 1 6
8 18 13
7 16 14


Output

103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370
#include<bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;
struct BIT{
    ll bit[maxn];
    ll query(int x){
        ll res = 0;
        for(++x; x > 0 ; x &= x - 1)res += bit[x];
        return res;
    }
    void update(int x , int val){
        for(++x; x <= 1e5 + 1 ; x += x & -x){
            bit[x] += val;
        }
    }
}s[2];

vector<int> val;
vector<int> adj[maxn];
ll res[maxn];
bool vis[maxn];
int n,a[maxn],b[maxn],c[maxn];
int sub[maxn] , big[maxn];
int FindRoot(int u){
    function<void(int,int)> dfs = [&](int u , int par){
        sub[u] = 1;big[u] = -1;
        for(auto & tmp : adj[u]){
            int c = a[tmp] + b[tmp] - u;
            if(vis[c] == 0 && c != par){
                dfs(c,u);
                sub[u] += sub[c];
                if(big[u] == -1 || sub[big[u]] < sub[c])big[u] = c;
            }
        }
    };
    dfs(u,0);
    int tot = sub[u];
    while(big[u] != -1 && sub[big[u]] >= tot / 2)u = big[u];
    return u;
}
void Centroid(int u){
    u = FindRoot(u);
    int root = u;
    function<void(int,int,int,int,bool)> dfs = [&](int u , int par , int C,int delta,bool add){
        s[0].update(C,1*delta);
        s[1].update(C,val[C]*delta);
//        cout << root << " " << u << " " << C << " " << delta << endl;
        if(u != root && add){
            res[root] += val[C];
        }
        for(auto & tmp : adj[u]){
            int c = a[tmp] + b[tmp] - u;
            if(vis[c] == 0 && c != par){
                dfs(c,u,min(C,::c[tmp]),delta,add);
            }
        }
    };
    vis[u] = 1;
    dfs(u , 0 , (int)val.size() - 1,1,1);
    for(auto & tmp : adj[u]){
        int c = a[tmp] + b[tmp] - u;
        if(vis[c] == 0){
            dfs(c,u,::c[tmp],-1,0);
            function<void(int,int,int)> dfs1 = [&](int u , int par , int C){
//                cout << root << " " << u << " " << C << " " << s[1].query(C) << " " <<
//                 (s[0].query(1e5)-s[0].query(C)) * val[C] << endl;
                res[u] += s[1].query(C);
                res[u] += (s[0].query(1e5)-s[0].query(C)) * val[C];
                for(auto & tmp : adj[u]){
                    int c = a[tmp] + b[tmp] - u;
                    if(vis[c] == 0 && c != par){
                        dfs1(c,u,min(C,::c[tmp]));
                    }
                }
            };
            dfs1(c,u,::c[tmp]);
            dfs(c,u,::c[tmp],1,0);
        }
    }
    dfs(u , 0 , (int)val.size() - 1,-1,0);
    for(auto & tmp : adj[u]){
        int c = a[tmp] + b[tmp] - u;
        if(vis[c] == 0)Centroid(c);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i < n ; ++i){
        cin >> a[i] >> b[i] >> c[i];
        val.pb(c[i]);
        adj[a[i]].pb(i);adj[b[i]].pb(i);
    }
    val.pb(1e9);
    sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
    for(int i = 1 ; i < n ; ++i){
        c[i] = lower_bound(val.begin(),val.end(),c[i])-val.begin();
    }
    Centroid(1);
    for(int i = 1 ; i <= n ; ++i)cout << res[i] << '\n';
}
