### ** 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.

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$

```
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
```

```
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
```

```
1
```

## Sample Output 3

```
0 0 0 0 0 0 0
```