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 REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
class UnionFind {
public:
    vector<int>rank, parent, sizes;
    //初期化
    UnionFind(int size) {
        rank.resize(size, 0);
        parent.resize(size, 0);
        sizes.resize(size, 1);
        rep(i, size)parent[i] = i;
    }
    //木の根を求める
    int find(int x) {
        if (parent[x] == x)return x;
        else return find(parent[x]);
    }
    //xとyの属する集合を併合 return [parent, child]
    pii unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)return { -1,-1 };
        if (rank[x] < rank[y]) {
            parent[x] = y;
            sizes[y] += sizes[x];
            return { y,x };
        }
        else {
            parent[y] = x;
            sizes[x] += sizes[y];
            if (rank[x] == rank[y])rank[x]++;
            return { x,y };
        }
    }
    //xとyが同じ集合に属するか否か
    bool same(int x, int y) {
        return (find(x) == find(y));
    }
};
// ============ template finished ============

pair<int, vector<vector<int>>> make_edges(vector<int>& parent) {
    const int N = parent.size();
    int root = -1;
    vector<vector<int>> edges(N);
    rep(i, N) {
        if (i == parent[i]) {
            root = i;
        }
        else {
            edges[i].push_back(parent[i]);
            edges[parent[i]].push_back(i);
        }
    }
    return { root,edges };
}

void dfs(
    const vector<vector<int>>& edges,
    const vector<ll>& funs,
    vector<ll>& sumfuns,
    const int now,
    const int par
) {
    sumfuns[now] = funs[now] + (par == -1 ? 0 : sumfuns[par]);
    for (auto child : edges[now]) if (child != par) {
        dfs(edges, funs, sumfuns, child, now);
    }
}

int main()
{
    ll N;
    cin >> N;
    vector<tuple<ll, ll, ll>> cabs;
    rep(_, N - 1) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        cabs.push_back(make_tuple(c, a, b));
    }
    sort(cabs.begin(), cabs.end(), greater<tuple<ll, ll, ll>>());

    UnionFind uf(N);
    vector<ll> funs(N, 0);
    for (auto cab : cabs) {
        ll c, a, b;
        tie(c, a, b) = cab;
        assert(!uf.same(a, b));
        int par, child;
        tie(par, child) = uf.unite(a, b);
        funs[child] += c * (uf.sizes[par] - 2 * uf.sizes[child]) - funs[par];
        funs[par] += c * uf.sizes[child];
    }
    int root;
    vector<vector<int>> edges;
    tie(root, edges) = make_edges(uf.parent);

    vector<ll> res(N, 0);
    dfs(edges, funs, res, root, -1);
    for (auto num : res)cout << num << endl;
    return 0;
}
