5 7
1 3 5
4 5 2
3 4 3
1 5 9
4 2 8
5 2 11
3 5 5

2

6 6
1 2 5
2 3 9
1 4 11
2 1 1000000
5 3 15
5 6 1

-1

4 7
1 2 5
1 1 30
3 2 9
1 4 11
1 4 16
2 1 1000000
1 4 11

4

2 0

-1

6 7
1 2 5
2 3 9
1 6 11
2 1 1000000
1 5 9
5 6 2
5 4 4

1

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

1

3 2
1 2 1
1 3 1

0