In the upcoming vacation, Marisa and Reisen plan to travel to a magical land. The magical land has $n$ popular locations connected by $n - 1$ bridges, any $2$ of the locations can travel to each other using the given bridges. In order to raise fund to preserve the magical land, the authority have imposed tolls on bridges, specifically, the $i$-th bridge will charge $w_i$ coins. Since Marisa and Reisen are both selfie enthusiasts, they have planned the travel schedule for their $n$ days vacation as follow: On day $i$-th $(1 \le i \le n)$, starting from location $1$, they will visit $i$ locations, check in and take photos. In order to save the traveling cost, each day they will choose $i$ location such that traveling between the locations is convenient and costs the least amount of coins. Each day, help Marisa and Reisen to compute the minimum number of coins they have to spend in order to complete the schedule.
### Input
- The first line consists of an integer $n$ $(1 \le n \le 5000)$.
- The next $n - 1$ lines, each line consists 3 integers $u, v,w$, there exists a bridge between locations $u$ and $v$ with cost $w$. $(1 \le u,v \le n, 1 \le w \le 10^9)$
### Output
- Contains $n$ lines, the $i$-th line contain the minimum cost to complete the schedule of the $i$-th day.
### Example
Input:
```
7
1 2 2
1 3 2
3 4 2
3 5 2
3 6 2
7 5 2
```
Output:
```
0
2
4
6
10
14
18
```
### Explanation
- On day $5$ , Marisa and Reisen will choose locations $1,2,3,5,7$. They will travel all the locations in the following order: $1$ $\rightarrow$ $2$ $\rightarrow$ $1$ $\rightarrow$ $3$ $\rightarrow$ $5$ $\rightarrow$ $7$ (Start at $1$, go to $2$, go back to $1$ and stop at $7$).
