제출 #15099

3 3
1 2 9
2 3 1
1 3 3
1 2

10

5

4 3
2 4 6
3 4 10
1 2 8
3 4

-1

34

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

-1

20