2021 ICPC Communication Routing Challenge: Marathon


A. Communication Routing Challenge
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
8 15 3 1
0 0 0 1 100 1050
1 1 0 1 200 2200
2 1 0 1 200 99400
3 2 0 3 100 450
4 3 0 3 500 1120
5 4 1 2 1000 40000
6 5 2 3 600 10000
7 5 2 3 600 10000
8 6 1 4 120 2500
9 6 1 4 120 450
10 7 1 5 170 1250
11 8 2 5 200 2500
12 9 3 5 100 1250
13 10 3 6 300 1150
14 11 3 7 300 1100
2 5 7
2 6 7
2 6 11
0 4 6 100
Output
1
0 8 0 3 13
----------------------------------------------------------------------------------------------------
