2
5 5 3 5
1 2 1 1
2 3 100 2
3 4 100 3
4 5 1 1
2 4 1 2
1 4
1 5
2 4
2 5
3 5
5 5 2 5
1 2 1 1
2 3 100 2
3 4 100 2
4 5 500 1
2 4 1 1
1 4
1 5
2 4
2 5
3 5

2
3
1
2
101
infinity
infinity
1
infinity
600