1 5 500 8
2 1 7
3 1 2
4 1 8
3 2 7
4 2 10
2 5 4
5 3 8
4 5 5
1
3 1 1