제출 #115196

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

-1

20

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

-1

10

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

15

12