제출 #109111

3 2
2 3 10
1 3 7
1 2

-1

27

4 2
1 3 10
1 4 1
3 4

-1

21

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

10

8