M. Minimum Path
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

After a successful expedition for a marathon at UFG, the competitors AlbertoTDNeto, duduFreire, EYZ, henriqueramos.qs, and MagePetrus made a pact: every time the 5 of them meet, they must roll a D100 (100-sided die). If the rolled number is 100, they must immediately go to Goiânia.

After many meetings, this finally happened, and the competitors will keep their promises. They all get into Henrique's car, which will drive them to Goiânia. The marathon runners want to take the shortest possible route from Brasília to Goiânia, of course. Additionally, since the car is quite heavy, Henrique is worried about the possibility of running out of fuel in the middle of the road. So, among the shortest paths, he wants a path that minimizes the longest distance the car will travel between two gas stations.

The gas stations are numbered from $$$1$$$ to $$$N$$$. Henrique will start from Brasília at gas station number $$$1$$$ and will finish his journey at gas station number $$$N$$$, in Goiânia. There are $$$M$$$ roads connecting pairs of distinct gas stations. For each $$$i$$$ from $$$1$$$ to $$$M$$$, road number $$$i$$$ starts from gas station $$$a_i$$$, leads to gas station $$$b_i$$$, and has a length of $$$w_i$$$ kilometers. It is only possible to travel this road in the direction from $$$a_i$$$ to $$$b_i$$$. It is guaranteed that there is a path from $$$1$$$ to $$$N$$$.

Help Henrique find a shortest path that minimizes the longest distance traveled between two consecutive gas stations.

Input

The first line contains two integers $$$2 \leq N, M \leq 2 \cdot 10^5$$$: the number of gas stations and the number of roads connecting pairs of distinct gas stations, respectively.

Next, there are $$$M$$$ input lines. The $$$i$$$-th of these lines contains three integers $$$a_i, b_i$$$, and $$$w_i$$$, with $$$1 \leq a_i, b_i \leq N$$$ and $$$1 \leq w_i \leq 10^5$$$, representing a one-way road from gas station $$$a_i$$$ to gas station $$$b_i$$$ with a length of $$$w_i$$$ kilometers.

Output

Print two integers, in this order: the length of the shortest path and the length of the longest edge traveled in a shortest path that minimizes the longest edge traveled.

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