34471번 - MIT Tour 서브태스크다국어

문제

Busy Beaver is visiting MIT, so he decided to have a tour around campus.

The campus consists of $N$ rooms and $N-1$ corridors between them. The rooms are enumerated consecutively from 1ドル$ to $N,ドル and the $i$-th corridor has a known length $w_i$ and can be traversed in both directions. The layout of campus is also such that between any two rooms, there is exactly one way to go from one to another through these corridors without going through any room twice. Define the level of a room to be the minimum number of corridors needed to get from the Great Dome (room 1ドル$) to this room. For instance, the Great Dome is level 0ドル,ドル and any room directly connected to it would be level 1ドル$. Let $k$ be the highest level of any room on campus, and denote $d(u, v)$ to be the length of the shortest path between rooms $u, v$.

Busy Beaver wants his tour to be interesting. Starting from the Great Dome (room 1ドル$), he wishes to visit a sequence of rooms $a_1, \dots, a_k$ such that for each 1ドル \leq i \leq k,ドル room $a_i$ is on level $i,ドル and for each 1ドル \leq i < k,ドル rooms $a_i, a_{i+1}$ are not connected by a corridor. As Busy Beaver is busy as usual, he also wants to minimize the total distance of the tour, which is $$d(1, a_1) + d(a_1, a_2) + \dots + d(a_{k-1}, a_k).$$

Since the MIT campus is very complex, Busy Beaver needs your help to plan out his tour. Help him find out the minimum length of an interesting tour.

입력

The first line consists of a single integer $N$ (2ドル \le N \le 2 \cdot 10^5$) --- the number of rooms at the MIT campus.

Each of the next $N-1$ lines contains three integers $u,ドル $v,ドル $w$ (1ドル \le u,v \le N,ドル $u \neq v,ドル 1ドル \le w \le 10^7$) --- a corridor between rooms $u$ and $v$ with the length $w$.

It is guaranteed that there is exactly one simple path between any two rooms, and that at least one interesting tour exists.

출력

Output a single integer, the minimal distance of an interesting MIT tour.

제한

서브태스크

노트

In the first test case, there are two possible interesting tours:

• $[a_1] = [2]$ --- The total distance of the tour will be 1ドル$.
• $[a_1] = [3]$ --- The total distance of the tour will be 1ドル$.

They both obtain the minimum possible length of 1ドル,ドル which is the answer for this case.

In the second test case, notice that both rooms of level 2ドル$ are connected to room 3ドル$. Therefore, no interesting tour can have $a_1 = 3,ドル or otherwise it will violate the condition that $a_1, a_2$ are not connected by a corridor. Therefore, there are two possible interesting tours:

• $[a_1, a_2] = [2, 4]$ --- The tour will traverse edges 1ドル\rightarrow 2\rightarrow 1\rightarrow 3\rightarrow 4$. The total distance is $d(1, a_1) + d(a_1, a_2) = 3 + 6 = 9.$
• $[a_1, a_2] = [2, 5]$ --- The tour will traverse edges 1ドル\rightarrow 2\rightarrow 1\rightarrow 3\rightarrow 5$. The total distance is $d(1, a_1) + d(a_1, a_2) = 3 + 7 = 10.$

Therefore, the minimum length of an interesting tour in this case is 9ドル$.