위험한 운전

면접 대비

시간 제한2초메모리 제한512 MB

요약

양방향 그래프에서 S에서 E로 가는 경로의 최대 위험 등급을 최소로 하고, 그중 총 거리도 최소인 경로를 찾습니다.

난이도: 보통10점 중 6점
유형: 그래프, 이분 탐색, 최단 경로, 그리디
정답자: 아직 제출이 없습니다

문제

영국의 겨울에 렌터카를 운전하다 보면, 내비게이션의 큰 도로 회피 옵션이 내가 원하는 것과 거의 반대라는 생각이 들 때가 있다. 큰 도로는 추운 겨울에는 눈이 치워질 가능성이 높고 따뜻한 겨울에는 침수될 가능성이 낮아, 위험이 더 적은 편이다.

나는 애프터눈 티를 위해 Hazel의 집에 가야 한다. 안전을 중시하므로 각 도로에는 위험도와 길이가 있다. 나는 경로에서 만나는 위험도의 최댓값을 최소화하는 경로를 원한다. 위험도의 최댓값을 최소화하는 모든 경로 중에서 경로의 총 길이를 최소화하는 경로를 원한다. 각 도로는 양방향이다. 내 집에서 Hazel의 집으로 가는 경로가 적어도 하나 있다. 내 집에서 Hazel의 집으로 가는 최적의 경로는 무엇인가?

입력

첫 번째 줄에는 4개의 정수 N (2 ≤ N ≤ 200 000), M (1 ≤ M ≤ 200 000), S (1 ≤ S ≤ N), E (1 ≤ E ≤ N)가 주어진다. N은 위치의 수, M은 도로의 수, S는 내 집의 위치, E는 Hazel의 집의 위치이며 S와 같지 않다.

다음 M개의 줄은 도로를 나타낸다. 각 줄에는 4개의 정수 A (1 ≤ A ≤ N), B (1 ≤ B ≤ N, A ≠ B), H (1 ≤ H ≤ 10^8), L (1 ≤ L ≤ 10^8)가 주어진다. A와 B는 도로의 양 끝점, H는 도로의 위험도, L은 도로의 길이이다.

출력

최적 경로의 위험도의 최댓값과 총 길이를 출력한다.

예제3

예제 1

입력

예상 출력

2
10

예제 2
입력
```
3 3 1 3
1 2 5 1
2 3 5 1
1 3 1 4
```
예상 출력
```
1
4
```
예제 3
입력
```
2 2 1 2
1 2 3 4
2 1 2 6
```
예상 출력
```
2
6
```