uva11934測資A

Input:
0 0 10 5 100
0 0 10 6 100
1 2 3 4 5
1 2 3 3 5
0 1 2 2 1
0 1 2 2 2
0 1 2 2 3
0 1 2 2 10
1 1 2 2 3
1 1 2 3 3
1 2 3 5 20
1 2 4 4 20
0 1 10 3 100
0 2 10 6 100
1 2 8 8 100
2 3 3 5 1000
2 3 5 5 1000
2 3 4 5 1000
3 4 5 12 1000
1 2 1 2 1000
3 5 6 36 1000
0 0 0 0 0
Output:
101
0
0
4
1
2
2
6
4
0
0
11
33
34
51
200
401
0
167
500
56