3 2 5
0 1 5 3
2 1 0 0
3 2 5
0 1 0 2
0 2 0 4
4 4 6
0 1 0 6
3 2 3 1
2 1 0 1
3 1 2 2
10 11 110
0 1 11 101
1 2 0 100
2 3 20 100
3 4 0 107
4 1 66 0
3 5 104 2
4 6 82 0
5 7 25 25
7 8 14 42
8 9 0 94
9 5 17 92
3 1 1
0 1 0 0

7
4
6
376
-1