Minimal Guardian Path

Problem Statement

A student named Little E wants to learn the art of calligraphy from a legendary master. The master lives at node \(n\) in a magical forest, which is represented as an undirected graph with \(n\) nodes and \(m\) edges. The nodes are numbered \(1, 2, \dots, n\) and the edges are numbered \(1, 2, \dots, m\). Initially Little E starts at node \(1\), and he must reach node \(n\) in order to meet the master.

The forest is inhabited by monsters. Every time someone passes through an edge \(e_i\), the monsters on that edge attack. Fortunately, at node \(1\) live two kinds of guardian spirits: type A and type B. If Little E carries a sufficient number of these spirits, the monsters will not launch an attack. Specifically, every edge \(e_i\) is associated with two threshold values \(a_i\) and \(b_i\). If Little E carries at least \(X\) type A guardians and at least \(Y\) type B guardians such that \(X \ge a_i\) and \(Y \ge b_i\), then he can safely pass that edge.

Little E needs to choose the numbers \(X\) and \(Y\) (which remain constant during his journey) so that there exists a path from node \(1\) to node \(n\) in which every edge \(e_i\) satisfies \(X \ge a_i\) and \(Y \ge b_i\). His goal is to minimize the total number of guardians carried, that is, to minimize \(X+Y\). If it is impossible for Little E to reach the master safely, output -1.

Input Format

The first line contains two integers \(n\) and \(m\), the number of nodes and edges respectively. Each of the following \(m\) lines contains four integers \(u\), \(v\), \(a_i\), and \(b_i\), indicating that there is an undirected edge between nodes \(u\) and \(v\) with guardian thresholds \(a_i\) and \(b_i\).

Output Format

Output a single integer --- the minimum value of \(X+Y\) required to safely travel from node \(1\) to node \(n\). If there is no such way, output -1.

Note

The cost for a particular path \(P\) is defined as \(\max_{e \in P}a_e + \max_{e \in P}b_e\). The answer is the minimum such cost over all paths from node \(1\) to node \(n\).

inputFormat

The first line contains two integers \(n\) and \(m\).

Each of the next \(m\) lines contains four integers \(u\), \(v\), \(a_i\), and \(b_i\), describing an undirected edge between nodes \(u\) and \(v\) with guardian thresholds \(a_i\) and \(b_i\).

It is guaranteed that \(1 \le u, v \le n\) and \(u \neq v\). There may be multiple edges between the same pair of nodes.

outputFormat

Output a single integer, which is the minimum total number of guardians (i.e. \(X+Y\)) needed so that Little E can safely travel from node \(1\) to node \(n\). If no valid path exists, output -1.

sample

3 3
1 2 3 4
2 3 4 3
1 3 5 5

8