J. Lead Time Estimation
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
8 11
2,7,2,6,5,1,2,7
6 7 2
0 1 4
0 2 2
1 3 6
1 4 5
1 5 3
2 4 1
3 6 2
3 7 9
4 5 2
5 7 2
Output
41,0,1,3,7
Input
6 7
10,8,9,10,11,12
0 1 1
1 2 2
1 3 3
1 4 4
2 5 5
3 5 6
4 5 7
6 7
10,8,9,11,11,12
0 1 1
1 2 2
1 3 4
1 4 4
2 5 5
3 5 7
4 5 7
Output
53,0,1,4,5
53,M