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

H. Hazardous Driving
PDF 题面可用

### 样例

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


NaN