El Granjero Juan ha comprado en línea recientemente un nuevo carro, pero en su afán él hizo dos veces "click" en el botón "submit" cuando estaba seleccionando accesorios para el carro, y como resultado el carro terminó equipado con dos sistemas de navegación. Peor aún, los dos sistemas frecuentemente hacen decisiones conflictivas acerca de la ruta que GJ debería tomar.

El mapa de la región en la cual GJ vive consiste de ~N~ intersecciones ~(2 \leq N \leq 10,000)~ y ~M~ caminos direccionales ~(1 \leq M \leq 50,000)~. El camino ~i~ conecta las intersecciones ~A_i~ ~(1 \leq A_i \leq N)~ y ~B_i~ ~(1 \leq B_i \leq N)~. Varios caminos pueden conectar el mismo par de intersecciones, y un camino bi-direccional (uno que permite ir en las dos direcciones) está representado por dos caminos direccionales separado en orientaciones opuestas. La casa de GJ está ubicada en la intersección ~1~ y su granja está ubicada en la intersección ~N~. GJ puede llegar a la granja desde su casa recorriendo a través de una serie de caminos direccionales.

Ambos unidades de GPS usan el mismo para descrito anteriormente; sin embargo, ellos tienen nociones diferentes acerca del tiempo de recorrido a través de cada camino. Toma ~P_i~ unidades de tiempo recorrer el camino ~i~ según la primera unidad GPS y ~Q_i~ unidades de tiempo de acuerdo a la segunda unidad (cada tiempo es un entero en el rango ~1..100,000~).

GJ quiere desplazarse desde su casa a la granja. Sin embargo, cada unidad GPS protesta bulliciosamente cada vez que GJ sigue un camino (por decir, de la intersección ~X~ a la intersección ~Y~) que la unidad GPS no cree que esté en la ruta más corta de ~X~ a la granja (aún es posible que ambas unidades GPS protesten, si GJ toma un camino que no le gusta a ninguna de las dos unidades).

Por favor, ayude a GJ a determinar el número mínimo del total de quejas que él puede recibir si elige su ruta apropiadamente.

Entrada

• Línea 1: Los enteros ~N~ y ~M~
• Líneas 2...M+1: La línea i+1 describe el camino ~i~ con cuatro enteros: ~A_i, B_i, P_i, Q_i~

Salida

El mínimo número total de quejas que GJ puede recibir si él elije una ruta óptima para ir de su casa a la granja.

Ejemplo de Entrada

5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5

Detalles de la Entrada: Hay ~5~ intersecciones y ~7~ caminos direccionales. El primer camino conecta la intersección ~3~ con la intersección ~4~; el primer GPS piensa que se recorre en ~7~ unidades y el segundo GPS piensa que se recorre en ~1~ unidad, etc.

Ejemplo de Salida

1

Detalles de la Salida: SI GJ sigue el camino ~1 \longrightarrow 2 \longrightarrow 4 \longrightarrow 5~, entonces el primer GPS se queja en el camino ~1 \longrightarrow 2~ (en su lugar preferiría el camino ~1 \longrightarrow 3~). Sin embargo, para el resto de la ruta ~2 \longrightarrow 4 \longrightarrow 5~, ambos GPS están contentos, desde que esta es la ruta más corta de ~2~ a ~5~ según cada GPS.