제출 #80150

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

8

5

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

-1

23

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

-1

23