제출 #80188

3 2
1 3 1
1 2 2
2 3

-1

5

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

9

16

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

-1

10