15 13
0 2 1000
1 2 1000
3 4 800
3 5 400
6 5 400
6 7 121
6 8 82
9 10 75
9 11 75
9 8 36
12 13 4
12 14 4
12 8 3