O-Speleologists
Our speleologists Toma and Miloš found out from certain sources that around “Three Hills” near Sombor town, exists entrance to cave which goes almost to the center of the Earth. But their only goal is to be written in Guinness Book of Records with biggest depth in cave exploring.
Cave is system of N halls and N-1 tunnels. First hall is numbered with 1, it is immediately after entering and it is on depth 0. From every hall it is possible to go to many other halls of bigger depth. There is only one way to each hall.
Image: mapa
InputIn the first row of standard input is integer N.
In each of the next N-1 rows there are three integers D1, D2 and VR.
D1 and D2 are hall numbers (D1 <> D2) and VR is depth difference between D1 and D2.
All numbers on input will be: (1 <= N, D1, D1, VR <= 100 000)
In each of the next N-1 rows there are three integers D1, D2 and VR.
D1 and D2 are hall numbers (D1 <> D2) and VR is depth difference between D1 and D2.
All numbers on input will be: (1 <= N, D1, D1, VR <= 100 000)
OutputIn the first output row You need to write what is the maximal depth of Cave.
In the next K rows You need to write numbers of halls from first to last on this deepest way. Input data will be so that solution is unique.
In the next K rows You need to write numbers of halls from first to last on this deepest way. Input data will be so that solution is unique.
Input:
Output
15
1 2 5
6 2 7
11 2 6
2 7 11
1 3 11
12 3 4
1 4 2
4 8 12
5 1 4
5 10 4
5 9 1
14 10 4
13 9 8
13 15 2Output
16
1
2
7Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.