4
1 2 1
2 3 2
3 4 4

11
9
9
17

7
1 2 5
1 3 2
1 4 8
3 5 4
3 6 1
4 7 6

38
63
40
62
60
45
92