나는 북극곰입니다

북극은 $N$개의 빙하와, 서로 다른 두 빙하를 잇는 $M$개의 얼음 다리로 이루어져 있다. 각 얼음 다리는 양방향으로 자유롭게 왕복할 수 있고, $i$번 얼음 다리의 길이는 $d_{i}$이다. 처음에는 서로 다른 두 빙하 사이를 왕복할 수 있는 경로가 반드시 존재한다.

북극곰의 사냥터는 1번 빙하이고, 집은 $N$번 빙하이다. 북극곰은 지금 1번 빙하에서 연어를 신나게 잡아먹고 있다. 그런데 지구 온난화로 얼음 다리가 무너지고 있어서, 서둘러 $N$번 빙하에 있는 집으로 돌아가야 한다는 것을 깨달았다.

북극곰은 매초 연어 1마리를 먹을 수 있고, 매초 길이 1만큼 움직일 수 있다. 연어는 1번 빙하에서만 먹을 수 있다.

북극곰은 이미 무너진 얼음 다리나 건너는 도중에 무너질 얼음 다리를 건널 수 없다. 다만 얼음 다리가 무너지는 시점과 건너기를 마치는 시점이 일치하면 그 다리를 건널 수 있다. 즉, 현재 $k$초가 지났고 건너려는 얼음 다리의 길이가 $d$이며 이 다리가 $t$초에 무너질 예정이라면, $k+d\leq t$를 만족해야 그 다리를 건널 수 있다.

연어가 너무 맛있어서 북극곰은 최대한 늦게까지 사냥터에 남아 연어를 먹고 싶어 한다. 얼음 다리 정보가 주어질 때, 북극곰이 먹을 수 있는 연어의 최대 수를 구하자.

첫 번째 줄에 빙하의 수 $N$과 얼음 다리의 수 $M$이 공백으로 구분되어 주어진다. ($2 \leq N \leq 100\,000$; $1 \leq M \leq 100\,000$)

두 번째 줄부터 $M$개의 줄에 걸쳐 얼음 다리 정보가 주어진다. 각 줄에는 정수 $u$, $v$, $d$, $t$가 공백으로 구분되어 주어지며, 이는 $u$번 빙하와 $v$번 빙하를 잇는 다리의 길이가 $d$이고 $t$초에 무너짐을 뜻한다. ($1 \leq u,v \leq N$; $u \neq v$; $1 \leq d \leq 10^{9}$; $1 \leq t \leq 10^{9}$)

북극곰이 $N$번 빙하의 집으로 돌아갈 수 있으면, 먹을 수 있는 연어의 최대 수를 출력한다. 집으로 돌아갈 수 없으면 -1을 출력한다.