Input 
3 5 1
2 3 2 3 17
2 3 2 2 16
2 2 2 3 3
3 3 1 1 12
1 3 3 17
Output 
0 28 12
Input 
4 3 1
3 4 1 3 12
2 2 3 4 10
1 2 4 16
Output 
0 -1 -1 12