시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB46191647.059%

문제

Mirko and Slavko are the only two contestants at the Grand Prix of Dabrovina Donja which is driven through nearby villages. The villages are connected via one-way roads, and for each road i we know Mi and Si, the time necessary for Mirko and Slavko to cross that road. The race itself is circular (meaning it starts and ends in the same village), but the route itself hasn't been determined yet. 

Mirko has bribed the organisers of the race so they'd pick a route in his favour. Specifically, the organisers are going to pick the shortest route (containing the minimal number of roads) such that Mirko is strictly faster than Slavko on that route. If, by any chance, there are several such routes, the organisers choose the one where Mirko gains maximal advantage. 

입력

The first line of input contains two integers N, M (2 ≤ N ≤ 300, 2 ≤ M ≤ N(N-1)), the number of villages and the number of connecting roads. 

Each of the following M lines contains 4 integers Ai, Bi, Mi, Si(1 ≤ Ai, Bi ≤ N, Ai ≠ Bi, 0 ≤ Si, Mi ≤ 106). Respectively, the initial and ending village of the ith road, the time necessary for Mirko and the time necessary for Slavko to cross that road. There won't exist two different roads that connect the same pair of villages in the same direction. 

출력

The first and only line of output must contain two integers: the shortest possible route (with the minimal number of roads) such that Mirko wins, and the maximal advantage Mirko can gain on a route of the shortest length. 

예제 입력 1

3 4
1 2 3 0
2 3 3 0
3 1 0 100
2 1 0 4

예제 출력 1

2 1

예제 입력 2

5 7
1 2 4 1
2 3 5 1
3 1 1 6
1 3 15 5
2 4 7 5
4 5 1 4
5 3 1 0

예제 출력 2

5 2

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #4 6번

  • 문제의 오타를 찾은 사람: jh05013