3
2 0
0 1 3000
4 1
0 1 81
1 2 41
2 3 59
9 2
0 1 1000
1 2 1200
0 3 1000
3 4 1200
0 5 1000
5 6 1200
0 7 1800
7 8 600

6000
200
13200