Busy Beaver está explorando el campus subterráneo del MIT. Hay $N$ edificios etiquetados del $1$ al $N$ y $M$ túneles etiquetados del $1$ al $M$ que conectan ciertos pares de edificios. El $i$-ésimo túnel conecta el edificio $a_i$ con el $b_i$. Para entrar en él, primero debes pagar $c_i$ monedas. Sin embargo, después de recorrer el túnel y apreciar su arte, eres recompensado con $r_i$ monedas.

Busy Beaver vive en el edificio $1$ y asistirá a su clase en el edificio $N$. ¿Cuál es el número mínimo de monedas que necesita llevar consigo para poder llegar al edificio $N$?

Ten en cuenta lo siguiente:

• Los túneles pueden recorrerse en cualquier dirección y cualquier número de veces. Cada vez que atraviesas un túnel, se incurre en el costo y se recibe la recompensa.
• Busy Beaver puede usar las monedas que recibe como recompensa para pagar futuras tarifas de entrada.
• Puede haber más de un túnel conectando dos edificios.
• Nunca puedes tener un número negativo de monedas.

Entrada

La primera línea contiene dos enteros separados por espacios, $N$ y $M$ ($2\le N \le 10^5$, $1\le M \le 2\cdot 10^5$).

Las siguientes $M$ líneas describen los túneles. La $i$-ésima línea consiste en cuatro enteros separados por espacios, $a_i$, $b_i$, $c_i$ y $r_i$ ($1 \le a_i,b_i \le N$, $a_i \ne b_i$, $0 \le c_i,r_i \le 10^9$).

Se garantiza que el edificio $N$ es alcanzable desde el edificio $1$ comenzando con un número finito de monedas.

Salida

Imprime una línea con la respuesta.

Subtareas

• ($20$ puntos) Hay $N-1$ túneles: un túnel que conecta el edificio $i$ con el edificio $i+1$ para todo $1 \le i < N$.
• ($20$ puntos) $r_i = 0$ para todo $1 \le i \le M$.
• ($20$ puntos) $c_i = r_i$ para todo $1 \le i \le M$.
• ($20$ puntos) $c_i \ge r_i$ para todo $1 \le i \le M$.
• ($20$ puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

3 3
1 2 2 1
2 3 3 0
1 3 5 0

Salida 1

4

Entrada 2

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

Salida 2

3

Entrada 3

3 4
1 2 4 3
1 2 4 6
2 1 5 4
2 3 10 9

Salida 3

4

Nota

Explicación del ejemplo 1

Si Busy Beaver comienza con $4$ monedas, puede atravesar primero el túnel del edificio $1$ al edificio $2$, pagando $2$ monedas y recibiendo $1$ moneda a cambio (por lo que tiene $4-2+1=3$ monedas al llegar al edificio $2$), luego puede atravesar el túnel del edificio $2$ al edificio $3$ usando sus $3$ monedas.

Explicación del ejemplo 2

Si Busy Beaver comienza con $3$ monedas, puede atravesar primero el túnel del edificio $1$ al edificio $2$, quedándose con $1$ moneda al llegar. Luego puede ir al edificio $3$, después de lo cual tiene $2$ monedas. Finalmente, puede llegar al edificio $4$ pagando $2$ monedas y recibiendo $4$ monedas al llegar.

Explicación del ejemplo 3

Busy Beaver puede comenzar en el edificio $1$ con $4$ monedas, atravesar el túnel $2$ tres veces, entrar al túnel $4$ con $10$ monedas y llegar al edificio $3$ con $9$ monedas. Se puede demostrar que Busy Beaver no puede llegar al edificio $3$ comenzando con menos de $4$ monedas.