Codah ClubВежбај. Испрати. Напредувај.
Најави се
Македонски
#0000A2

z-streets

Mr. Little Z and Mister S want to travel from town Izelgard to Deronjilous city. In their journey, they will be passing through some streets. Each street has a length and an average height of the trees on it. Any two of the M streets could be connected by some of N endpoints (intersections). The town Izelgard will be represented as an endpoint with the index 1 and Deronjilous city will be represented as an endpoint with the index N.


Mr. Little Z likes to travel along the shortest path and Mister S likes to travel along the streets that have very tall trees.


We will say that some street along the path is the highest street along the path if average height of the trees on the street is maximal of all average heights of the trees on the streets along the path. We will introduce a term "the highest average" of the path as the highest value of all the average heights of the trees on all the streets along the path.


In order to satisfy both of them, they have decided to choose a path that is the shortest of all possible paths from town Izelgard to Deronjilous city (if any path exists at all) and if there are more such paths, then they choose a path that has maximal "highest average" of all the shortest paths.


InputThe first line of the standard input contains two space-separated integers: N (2 <= N <= 10 000) and M (1 <= M <= 50 000). Next M lines describe the streets (lines from 2 to M + 1). Line i contains four space-separated integers: ai, bi, leni and hi. It means there is a bidirectional street from endpoint ai (1 <= ai <= N) to endpoint bi (1 <= bi <= N, ai != bi) with length leni (1 <= leni <= 100 000) and average height of the trees of hi (1 <= hi <= 100 000). There will not be i and j, i != j, such that (ai = aj and bi = bj) or (ai = bj and bi = aj).

OutputOn the standard output you should print two space-separated integers: the shortest path and maximal "highest average" of all the shortest paths; if there is no any path from town Izelgard to Deronjilous city output -1 for both values.

Input:
9 12
1 2 1 5
1 3 2 8
1 4 3 2
2 6 5 3
3 5 2 12
4 5 1 22
4 9 9 9
5 7 3 1
6 7 1 10
6 8 1 2
7 9 5 8
8 9 100 100
Output:
12 22
Explanation:
There are 4 shortest paths, each of length 12. All shortest paths (represented by their endpoints) are:
1-2-6-7-9
1-3-5-7-9
1-4-5-7-9
1-4-9

We choose the 3rd path because its highest average is 22, that is greater than highest average of all the other shortest paths.


Input:
5 8
5 4 1 1
5 3 1 1
5 2 1 1
4 3 1 1
4 1 1 1
3 2 1 1
3 1 1 1
2 1 1 1
Output:
2 1
Explanation:
All paths have highest height 1.


Input:
4 3
1 2 10 10
1 3 10 10
2 3 15 5551
Output:
-1 -1
Explanation:
There is no any street associated with Deronjilous city.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.