마법의 숲

서예 대가의 진정한 가르침을 얻기 위해, 꼬마 E는 마법의 숲에 사는 은둔자를 찾아가기로 했다. 숲은 n개의 정점과 m개의 간선으로 이루어진 무방향 그래프로 나타낼 수 있다. 정점에는 1, 2, 3, …, n의 번호가 붙어 있고, 간선에는 1, 2, 3, …, m의 번호가 붙어 있다. 처음에 꼬마 E는 정점 1에 있고, 은둔자는 정점 n에 살고 있다. 은둔자를 만나려면 꼬마 E는 먼저 이 마법의 숲을 지나가야 한다.

숲에는 고블린이 많다. 사람이 어떤 간선을 지날 때마다 그 간선에 있는 고블린이 습격한다. 다행히 정점 1에는 두 종류의 엘프 수호자가 살고 있다. A형 엘프와 B형 엘프다. 꼬마 E는 이들의 힘을 빌려 목표에 도달할 수 있다.

꼬마 E가 충분히 많은 수호 엘프를 데리고 다니면 고블린은 그를 습격하지 않는다. 일반적으로 무방향 그래프의 각 간선 ei에는 두 값 ai와 bi가 대응된다. 꼬마 E가 데리고 다니는 A형 엘프의 수가 ai 이상이고 B형 엘프의 수가 bi 이상이면, 숲의 이 간선에서 고블린은 그를 습격하지 않는다. 꼬마 E가 지나는 모든 간선에서 습격을 받지 않을 때에만 은둔자를 찾아가는 여정이 성공했다고 본다.

수호 엘프를 데리고 다니는 것은 큰 부담이므로, 꼬마 E는 은둔자에게 성공적으로 도달할 수 있으면서 데리고 갈 수 있는 엘프의 최소 총수를 알고 싶어 한다. 엘프의 총수는 A형 엘프의 수와 B형 엘프의 수를 더한 값이다.

입력의 첫 줄에는 무방향 그래프의 정점 수와 간선 수를 나타내는 두 정수 n과 m이 주어진다.

다음 m개의 줄에서 i + 1번째 줄에는 공백으로 구분된 4개의 양의 정수 Xi, Yi, ai, bi가 주어지며, 이는 i번째 간선이 정점 Xi와 Yi를 잇는다는 뜻이다. ai와 bi의 의미는 위에서 설명한 것과 같다.

정수 하나를 출력한다. 꼬마 E가 은둔자에게 성공적으로 도달할 수 있으면 데리고 가야 하는 엘프 총수의 최솟값을 출력한다. 그렇지 않으면 "-1"을 출력한다(따옴표는 출력하지 않는다).

• 2 ≤ n ≤ 50000
• 0 ≤ m ≤ 100000
• 1 ≤ ai, bi ≤ 50000