시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB2610975.000%

문제

When driving a hire car in the UK in winter, it has sometimes struck me that the navigation system’s option of avoiding major roads is almost the opposite of what I want. Major roads tend to be less hazardous, being more likely to be cleared of snow in cold winters and less likely to be flooded in warm winters.

I need to get to Hazel’s house for afternoon tea. Given my emphasis on safety, each road will have a hazard rating and a length. I want a route that minimises the maximum hazard rating encountered on the route. Out of all the routes that minimise the maximum hazard rating encountered, I want one that minimises the total length of the route. Each road is two-way. There is at least one route from my house to Hazel’s house. What is an optimal route to get from my house to Hazel’s house?

입력

The first line contains 4 integers N (2 ≤ N ≤ 200 000), which is the number of locations, M (1 ≤ M ≤ 200 000), which is the number of roads, S (1 ≤ S ≤ N), which is the location of my house, and E (1 ≤ E ≤ N), which is the location of Hazel’s house (and is not equal to S).

The next M lines describe the roads. Each of these lines contains 4 integers A (1 ≤ A ≤ N), which is one endpoint of the road, B (1 ≤ B ≤ N, A 6= B), which is the other endpoint of the road, H (1 ≤ H ≤ 108), which is the hazard rating of the road, and L (1 ≤ L ≤ 108), which is the length of the road.

출력

Display the maximum hazard rating of an optimal route and its total length.

예제 입력 1

4 5 1 4
1 2 1 5
2 4 2 10
1 3 2 5
3 4 2 5
1 4 5 4

예제 출력 1

2
10

예제 입력 2

3 3 1 3
1 2 5 1
2 3 5 1
1 3 1 4

예제 출력 2

1
4

예제 입력 3

2 2 1 2
1 2 3 4
2 1 2 6

예제 출력 3

2
6