15 18 8
1 2 5
2 3 1
3 4 1
4 1 5
1 5 1
5 6 1
1 7 1
7 8 100
8 9 1
9 10 1
1 10 1
1 15 2
15 10 100
10 14 1
14 13 5
13 12 5
12 11 1
11 10 1
4 12
12 14
2 4
3 6
1 10
7 9
8 9
10 15

8
3
2
8
1
3
1
3