2
9
500
450
600
1000
950
800
1200
700
1500
12
6 1 15000 0 180
6 3 40000 290 120
1 2 60000 10 190
2 3 70000 210 45
3 5 45000 270 90
5 8 78000 330 170
3 4 36000 10 190
8 4 78000 70 220
2 4 18000 280 100
2 7 68900 350 170
4 7 60000 40 220
4 9 95000 330 120
6 9
5
700
900
250
1000
750
7
1 2 10000 10 45
2 3 20000 30 0
1 5 10000 180 90
2 5 5000 45 200
2 4 40000 35 20
5 4 35000 200 300
3 4 30000 125 65
1 4