2019 XCPC Newbie Selection #1 (South Pacific ICPC Regional Finals 2018)

H. Hazardous Driving
PDF 题面可用
你可以在这里下载。

单点时限: 6.0 sec

内存限制: 512 MB

样例

Input
4 5 1 4
1 2 1 5
2 4 2 10
1 3 2 5
3 4 2 5
1 4 5 4
Output
2
10
Input
3 3 1 3
1 2 5 1
2 3 5 1
1 3 1 4
Output
1
4
Input
2 2 1 2
1 2 3 4
2 1 2 6
Output
2
6