31932번 - 나는 북극곰입니다

문제

북극은 총 $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을 출력한다.

제한

힌트