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 MOD 1000000007
#define int long long
#define pb push_back
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> edge;
const int N=100005;
int n,par[N],sz[N],ans[N],lazy[N]; vector<edge> e; vector<int> child[100001];
int getp(int u) {
	if (u==par[u]) return u;
	return par[u]=getp(par[u]);
}
void joint(int u,int v,int val) {
	if (sz[u]>sz[v]) swap(u,v);
	//Now we only have to merge u into v
	while (child[u].size()) {
		child[v].pb(child[u].back());
		int temp=child[u].back();
		if (lazy[u]) ans[temp]+=lazy[u];
		ans[temp]+=val*sz[v];
		ans[temp]-=val*sz[u];
		ans[temp]-=lazy[v];
		child[u].pop_back();
	}
	lazy[v]+=sz[u]*val;
	sz[v]+=sz[u];
	par[u]=v;
}
signed main() {
	//freopen("aome.inp","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n;
	fw (i,1,n) {
		int a,b,c; cin>>a>>b>>c; a--; b--;
		e.pb(edge(c,ii(a,b)));
	}
	sort(e.begin(),e.end());
	reverse(e.begin(),e.end());
	/*
	Idea: Sort all edges based on their c values. Then if a and b doesn't belong to the same group,
	every item in b will connect to every item in a with a cost ofc.
	Merge the smaller group into the bigger one, so each item will be merged exactly log(N) times.
	To update the smaller group, just do it manually. To update the bigger group, we keep a lazy value
	for it, so if we need to update it later when merging we will also perform the lazy update.
	Call the larger group u, smaller one v. Every item in v is added c * sz[u], and otherwise.
	To successfully use lazy, erase all the elements in v by the supposed lazy value we will add.
	*/
	fw (i,0,n) {
		child[i].pb(i);
		sz[i]=1;
		par[i]=i;
		ans[i]=0;
		lazy[i]=0;
	}
	fw (i,0,e.size()) {
		int c=e[i].first,u=e[i].second.first,v=e[i].second.second;
		int pu=getp(u),pv=getp(v);
		if (pu==pv) continue;
		joint(pu,pv,c);
	}
	fw (i,0,n) ans[i]+=lazy[getp(i)];
	fw (i,0,n) cout<<ans[i]<<"\n";
}