题目描述

塔图因星球上有 $n$ 座小镇，由 $n-1$ 条双向道路连接，形成一个联通无向图。

第 $i$ 条道路连接小镇 $A_i$ 和 $B_i$，并且有一个容量 $C_i$，表示运送货物的重量上限是 $C_i$ 千克。

对于每两座小镇 $x,y$，定义 $F(x,y)$ 表示从 $x$ 向 $y$ 能够一次性运送的货物重量上限值。

请你对于每条道路求出，在只断掉它而保留其他所有道路的情况下，所有 $F(x,y)$ 的总和。

注意 $F(x,y)$ 是无序对，且 $x \neq y$。如果连一千克货物都运送不了，那么 $F(x,y) = 0$。

输入格式

第一行，一个正整数 $n$，表示小镇个数。 接下来 $n-1$ 行，每行三个正整数，依次为 $A_i,B_i,C_i$。

输出格式

共 $n-1$ 行，每行一个整数，表示断掉这条边之后的答案。

请按照边的输入顺序进行输出。

样例

见下发文件。

数据范围

对于所有数据，$1 \leq 8 \times 10^5,1 \leq A_i \neq B_i \leq n,1 \leq C_i \leq 20$。