제출 #41045

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

7

4

5 4
2 5 3
1 2 10
2 3 2
2 4 7
4 2

-1

27

5 5
1 5 1
1 2 9
1 3 5
3 5 3
3 4 9
2 3

-1

25