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