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>

using namespace std;

#define int long long

typedef pair<int,int> ii;
typedef pair<int,ii> iii;

int n;
ii c[100001], e[100001];
int p[100001], sz[100001], id[100001];
vector<ii> z[200001];
int f[100001];

int anc(int x)
{
	if (p[x] == x) return x;
	return p[x] = anc(p[x]);	
}

void join(int x,int y,int z)
{
	sz[anc(y)] += sz[anc(x)];
	p[anc(x)] = anc(y);
	id[anc(y)] = z;
}

void dfs(int u,int p,int cur)
{
	if (1 <= u && u <= n)
	{
		f[u] = cur;
		return;
	}	
	for (int i=0;i<z[u].size();i++)
	{
		int val = z[u][i].first;
		int v = z[u][i].second;
		if (v != p)
			dfs(v,u,cur + val);
	}
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i=1;i<=n;i++)
	{
		p[i] = i;
		sz[i] = 1;
	}
	for (int i=1;i<=n-1;i++)
	{
		int u,v,cost;
		cin >> u >> v >> cost;
		c[i] = ii(cost,i);
		e[i] = ii(u,v);
	}	
	sort(c+1,c+1+n-1);
	for (int i=n-1;i>=1;i--)
	{
		int val = c[i].first;
		int u = e[c[i].second].first;
		int v = e[c[i].second].second;
		if (sz[anc(u)] == 1) z[i+n].push_back(ii(val*sz[anc(v)],u));
		else z[i+n].push_back(ii(val*sz[anc(v)],id[anc(u)]+n));
		if (sz[anc(v)] == 1) z[i+n].push_back(ii(val*sz[anc(u)],v));
		else z[i+n].push_back(ii(val*sz[anc(u)],id[anc(v)]+n));
		join(u,v,i);
	}
	dfs(n+1,-1,0);
	for (int i=1;i<=n;i++)
		cout << f[i] << '\n';
}