시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 128 MB60317214530.146%

문제

정우는 대회 준비를 위해 중앙대학교에서 숭실대학교까지 가려 한다. 그런데 중앙대학교에서 숭실대학교까지 가기 위해서는 몇 개의 거점을 지나쳐야 한다. 각 거점을 경유할 시 발생하는 10분간 기본요금과 1분당 추가요금은 모두 다르다. 정우는 숭실대학교까지 가장 적은 비용을 사용해서 도착하려 한다. 정우를 위하여 중앙대학교에서 숭실대학교까지 가는 최소 비용과 거쳐야 하는 거점의 수를 알아내는 프로그램을 작성하자.

입력

첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R개의 줄에 걸쳐 각 경로에 대한 정보 (a, b, c, d, e)가 순서대로 주어진다. a는 시작 거점, b는 도착 거점, c는 기본요금, d는 1분당 추가요금, e는 걸리는 시간이다. (1 ≤ a, b ≤ 100, 1 ≤ c, d, e ≤ 100) 단, c, d, e는 정수이다.

출력

첫 번째 줄에 최소 비용과 거쳐야 하는 거점의 수를 차례대로 출력한다. 중앙대학교부터 숭실대학교까지 도착할 방법이 없을 경우에는 'It is not a great way.'를 출력한다. 단, 최소 비용 경로가 여러 가지 존재하면 거점의 수를 최소화하여 출력해야 한다.

예제 입력 1

3 3
1 2 3 1 12
1 3 5 2 20
2 3 3 2 8

예제 출력 1

8 3

예제 입력 2

4 2
1 2 5 2 11
2 3 8 1 21

예제 출력 2

It is not a great way.

출처

University > 숭실대학교 > 2018 SCAL-MOOKJA C번

University > 중앙대학교 > 2018 SCAL-MOOKJA C번