input:

4 3 6
1 2 1
2 3 3
3 4 2
1 2
1 3
1 4
2 3
2 4
3 4

output:

3 4
3 4
3 4
3 4
3 4
2 2

result:

wrong answer 1st lines differ - expected: '1 2', found: '3 4'