GPS 대결

FJ가 새 차를 주문하면서 GPS 내비게이션을 두 번 담았습니다. 두 GPS는 같은 지도를 쓰지만, 각 도로의 이동 시간을 다르게 계산합니다.

지도는 $N$개 교차로 ($2 \le N \le 10\,000$)와 $M$개의 단방향 도로 ($1 \le M \le 50\,000$)로 이루어집니다. 도로 $i$는 $A_i$에서 $B_i$로 이어집니다. 같은 교차로 쌍을 잇는 도로가 여러 개일 수 있고, 양방향 도로는 반대 방향의 두 단방향 도로로 주어집니다. FJ의 집은 1번, 농장은 $N$번 교차로입니다. 1에서 $N$까지 도로만으로 도달할 수 있습니다.

도로 $i$를 지나는 데 첫 GPS는 $P_i$, 두 번째 GPS는 $Q_i$ 시간이 걸립니다 (각각 $1 \ldots 100\,000$ 정수).

FJ가 집에서 농장으로 갈 때, 각 GPS는 자신이 보기에 $X$에서 농장까지 최단 경로에 포함되지 않는 도로를 지나면 불평합니다. 두 GPS가 모두 불평하면 $+2$로 셉니다.

경로를 적절히 고르면 받을 수 있는 불평 횟수의 최솟값을 구하세요.

• 1번째 줄: $N$, $M$.
• 다음 $M$줄: $A_i$, $B_i$, $P_i$, $Q_i$.

최소 총 불평 횟수.

각 GPS마다 농장까지의 최단 거리를 미리 구한 뒤, 도로가 최단 경로 DAG에 포함되는지로 불평 여부를 정할 수 있습니다.