题目描述

有一棵 $n$ 个点的树，每条边有一流量限制。令某一个点为根节点，向根节点灌水，最终从叶子节点流出的水量和为这一个点的最大流量，请求出每个点的最大流量。

输入格式

第一行一个整数 $n$ 表示点的数目。

接下来 $n−1$ 行，每行三个整数 $x,y,z$ 描述一条连接 $x,y$ 的流量限制为 $z$ 的树边。

输出格式

输出共 $n$ 行。

第 $i$ 行表示编号为 $i$ 的最大流量。

Samples

5
1 2 3
1 5 1
2 3 2
2 4 2

4
5
2
2
1

数据规模

对于所有数据，保证 $2≤n≤10^5,1≤x,y≤n,1≤z≤10^9$。

数据保证读入的是一棵树。