Rainbow Road (Extreme)

Description

Whiterabbit like rainbows, and thus wants to travel on a rainbow journey across Bunnyland. In Bunnyland, there are $N$ cities connected by $N − 1$ roads. The roads are constructed in such a way that there is $1$ unique way to get from any city to any other city using only the roads. The $i^{th}$ road connects cities $A_i$ and $B_i$, but since Whiterabbit only cares about the $7$ colours in the rainbow, he interprets the $i^\text{th}$ road as having a colour $C_i$ that is between $1$ and $7$ inclusive.

Whiterabbit will pick some starting city $S$ and some ending city $E$. He will then travel from $S$ to $E$ using only the roads along the unique path between those $2$ cities. The quality of the journey is the number of distinct colors of the roads he travels along.

For all qualities from $1$ to $7$, help Whiterabbit determine the number of different journeys he can take in Bunnyland with that quality. $2$ journeys are considered distinct if their start cities differ or their end cities differ.

Input

The first line contains one integer $N$.

Then, $N-1$ lines follow, each representing a road. The $i^\text{th}$ line contains $3$ integers $A_i$, $B_i$ and $C_i$.

Output

Print $7$ integers, the $i^\text{th}$ integer is the number of journeys with quality $i$.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq A_i,B_i \leq N$
• $1 \leq C_i \leq 7$

Sample Input 1

9
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 6
7 8 7
7 9 7

Sample Output 1

18 14 12 10 8 6 4

Sample Input 2

12
1 2 3
2 3 6
3 4 7
4 5 1
5 6 2
6 7 1
7 8 2
8 9 4
9 10 5
10 11 3
11 12 6

Sample Output 2

22 26 22 20 18 12 12

Sample Input 3

1

Sample Output 3

0 0 0 0 0 0 0