고유한 능력

Emma는 평화롭고 기술이 발달한 Shu 나라에 살고 있다. 이 나라에는 $N$개의 도시가 있고, 양방향 도로 $M$개로 연결되어 있다. 도로 $i$의 한쪽 끝에서 다른 쪽 끝까지 지나는 데는 정확히 $T_i$분이 걸린다. 이 도로들을 이용하면 어느 도시에서든 다른 모든 도시에 갈 수 있다.

Shu 나라의 모든 주민에게는 정수 형태의 집단 식별자가 배정되어 있다. 정부가 주민의 이동을 더 잘 통제하려는 것이다. 각 도로에는 보안 시스템이 설치되어 있어서, 집단 식별자가 $P_i$인 사람만 그 도로를 지날 수 있다. 다른 식별자를 가진 사람은 그 도로를 쓸 수 없다. 정부는 이 시스템이 수세기 동안 이 나라를 괴롭혀 온 도로 혼잡을 줄여 줄 것이라고 믿는다.

Emma의 집단 식별자는 처음에 1이다. 그녀에게는 특별한 능력이 있다. 식별자를 원하는 임의의 정수로 바꿀 수 있다. 해킹을 하는 것이 아니다. 식별자를 $a$에서 $b$로 바꾸려면 도시에 가만히 머물며 정확히 $|a-b|$분 동안 명상하면 된다. 이 변경은 도시에 있을 때만 할 수 있고, 도로 위에서는 할 수 없다.

Emma는 도시 1에 있고, 도시 $N$에 있는 친구를 만나려 한다. 정부의 의심을 피하려면 도시 $N$에 도착한 뒤 식별자를 다시 1로 되돌려야 한다(식별자를 바꾼 경우에 한해서이다).

도시 1에서 도시 $N$까지 Emma가 이동하는 데 걸리는 최소 시간을 구하라.

첫 줄에 도시 수 $N$과 도로 수 $M$이 주어진다($2 \le N \le 200000$, $N-1 \le M \le 200000$). 이어지는 $M$개의 줄에는 정수 네 개 $A_i$, $B_i$, $P_i$, $T_i$가 주어진다($1 \le A_i, B_i \le N$, $A_i \ne B_i$, $1 \le P_i, T_i \le 10^9$). 각 줄은 도시 $A_i$와 도시 $B_i$를 잇는 양방향 도로를 뜻하며, 이 도로는 $T_i$분이 걸리고 집단 식별자가 $P_i$인 사람만 이용할 수 있다. 어떤 도시에서든 다른 모든 도시에 도달할 수 있다.

도시 1에서 도시 $N$까지 이동하고, 식별자를 1로 되돌린 채 여행을 끝내는 데 걸리는 최소 시간을 정수 하나로 한 줄에 출력한다.