시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 356 29 21 20.388%

문제

월드산의 하부에는 동굴로 들어가는 입구가 있는데, 동굴은 터널을 통해 서로 연결되어 있는 여러 개의 작은 방들로 구성되어 있다. 동굴 입구는 탐험의 시작점이 되는 방 (이하 시작방)으로 곧장 연결되어 있다. 각 방을 연결하는 터널은 서로 교차하지 않으며, 두 개의 방을 연결하는 터널은 많아 봐야 하나이다.

"원쌤배 동굴 탐험 대회"가 개최될 예정이다. 대회의 목표는 시작방에서 출발하여 동굴 내부를 달려, 다시 시작방으로 되돌아 와 빠져 나오는 것인데, 그 경로는 참가자가 마음대로 정할 수 있지만 두 가지 조건을 지켜야 한다. 첫째 조건은, 시작방 이외의 방을 최소한 하나는 거쳐야 한다는 것이며, 둘째 조건은, 어떤 방과 터널도 최대 한 번밖에 방문할 수 없다는 것이다. (시작방은 물론 두 번 방문하게 되므로 예외이다.)

유명한 동굴 탐험가 김진영은 대회에 참가하기 위해 오랜 준비를 했고, 동굴을 여러 번 사전 답사하여 동굴 내부 구조를 알아내는 데 성공했다. 각각의 터널에 대해, 그는 그 터널을 가로지르는 데 필요한 시간을 계산했는데, 터널을 어느 방향으로 가로지르느냐에 따라 걸리는 시간이 서로 다른 경우도 있을 수 있다고 한다. 동굴 입구와 시작방 사이에서 소요되는 시간이나, 방 내부에서 이동하는데 필요한 시간은 무시할 수 있을 만했다. 이제 그는 경기의 규칙을 만족시키면서도, 가장 짧은 시간 내에 완주할 수 있는 경로를 찾아내려고 한다. 그를 돕기 위한 프로그램을 작성하라.

입력

첫째 줄에 n과 m이 주어진다. (3≤n≤5000, 3≤m≤10000) 이는 각각 동굴 내부의 방의 개수와, 터널의 개수를 나타낸다.
  이어지는 m개의 줄에는 각각 터널의 정보를 제공하는 네 개의 숫자 a, b, c, d가 포함되어 있다. 이것은 a번 방에서 b번 방으로 갈 때는 c의 시간이 걸리고, 반대로 b번 방에서 a번 방으로 갈 때는 d의 시간이 걸린다는 의미이다. (1≤a, b≤n. a≠b. 1≤c, d≤10000)
  방의 번호는 1번부터 n번까지 연속하여 붙어 있으며, 1번 방이 시작방이다. 언제나 조건을 만족하는 경로가 하나는 있다고 가정해도 좋다.

출력

동굴 탐험에 소요되는 최소시간을 출력한다.

예제 입력

3 3
1 2 4 3
2 3 4 2
1 3 1 1

예제 출력

6

힌트