5 7
1 2 5
1 3 10
2 3 20
3 5 30
3 4 25
4 5 35
1 5 15
4
1 2
3 5
1 5
2 4