동굴 탐험

월드산 아래에는 동굴 입구가 있고, 입구는 탐험을 시작하는 1번 방으로 바로 이어진다. 동굴 안에는 여러 개의 작은 방이 있으며, 방들은 터널로 연결되어 있다. 터널끼리는 서로 교차하지 않고, 같은 두 방을 잇는 터널은 최대 하나만 존재한다.

동굴 탐험 경기는 1번 방에서 출발해 동굴 안을 이동한 뒤 다시 1번 방으로 돌아와 밖으로 나오는 방식으로 진행된다. 참가자는 경로를 자유롭게 정할 수 있지만 다음 조건을 모두 지켜야 한다.

• 1번 방이 아닌 방을 적어도 하나 방문해야 한다.
• 1번 방을 제외한 어떤 방도 두 번 이상 방문할 수 없다.
• 어떤 터널도 두 번 이상 지날 수 없다.

1번 방은 출발할 때와 도착할 때 방문하므로 예외적으로 두 번 방문한다.

각 터널을 지나는 데 걸리는 시간은 방향에 따라 다를 수 있다. 동굴 입구와 1번 방 사이의 이동 시간, 그리고 방 안에서 이동하는 시간은 무시한다. 조건을 만족하는 경로 중 총 이동 시간이 가장 짧은 값을 구하라.

첫째 줄에 방의 개수 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번 방이 시작방이다. 조건을 만족하는 경로가 항상 하나 이상 존재한다.

동굴 탐험을 완료하는 데 필요한 최소 시간을 출력한다.