Firefighting

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

4
1 8 3 6

9 26
2 1 21
2 9 21
2 8 21
2 3 56
3 4 37
4 5 29
7 6 25
6 4 24

4
5 6 2 3

3 18
1 2 35
2 3 49

3
1 2 3

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

2
4 10