8 13
2
3 8
1 2 2
1 3 3
1 4 7
2 3 2
2 4 3
2 5 4
3 6 4
3 7 3
4 5 1
6 5 1
6 8 2
5 8 4
7 8 2

7 10 1 2
1 3 2
1 4 4
2 3 3
2 5 1
2 6 3
2 7 3
3 4 4
3 6 4
4 6 5
5 7 2

5 6 2
1 5
3 5 1
1 5 5
1 2 6
1 4 8
4 5 9
2 4 2

3 2 3
1 2 3
1 3 1
2 3 4