input3.txt

15
17
0 3 50
1 3 51
2 6 52
3 5 53 
5 4 54
4 11 55
4 8 56
5 6 57
6 7 58
7 8 59
7 9 60
8 10 61
10 11 62
10 12 63
9 12 64
11 13 65
12 14 66
-1
-1
-1
1
0
0
6
0
6
7
0
3
2
-2
-2