题目描述

给定一棵n个节点的树，求其中每个点到其他节点的距离和。

输入格式

第一行一个整数n； 接下来n-1行是三个数x,y,z，表示x到y有一条长度为z的边； 数据保证给出的是一棵树。

输出格式

n行，一行一个数，第i个表示点i到其他点的距离和。

样例数据

input

3
1 2 3
1 3 5

output

8
11
13

数据规模与约定

1<=n<=100000; 1<=z<=max int;