Hazardous Driving

Interview

Time limit2sMemory limit512 MB

Summary

Given an undirected weighted graph, find an S to E route minimizing its maximum edge hazard, and among those the minimum total length.

Level: Medium6 of 10
Topics: Graph, Binary search, Shortest path, Greedy
Solved: No attempts yet

Problem

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 has 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?

Input

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 ≠ B), which is the other endpoint of the road, H (1 ≤ H ≤ 10^8), which is the hazard rating of the road, and L (1 ≤ L ≤ 10^8), which is the length of the road.

Output

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

Examples3

Example 1

Input

Expected output

2
10

Example 2
Input
```
3 3 1 3
1 2 5 1
2 3 5 1
1 3 1 4
```
Expected output
```
1
4
```
Example 3
Input
```
2 2 1 2
1 2 3 4
2 1 2 6
```
Expected output
```
2
6
```