D2. Networking (hard version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Example
Input
7 5 4
2 1 5
1 4 9
1 7 6
2 5 7
7 3 3
2 6 2
2 3 8
3 4 10
4 6 5
3 1 2
6 1 10
Output
0 5 2 9
5 0 7 7
2 7 0 10
9 7 10 0