7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
8 15
1 2 10
1 3 5
1 7 15
2 4 9
2 5 15
2 3 4
3 7 4
3 5 8
3 8 6
7 8 30
4 6 10
4 5 15
5 6 10
5 8 15 
8 6 10
1 6 200
0 0