3 3
10
0 1 1
1 2 1
2 3 4
3 2 3
2 1 3
1 0 2