En la base de la montaña de Mt.Byte hay una entrada a una cueva. La cueva consiste de un sistema complejo de cámaras conectadas con túneles. La entrada de la cueva conduce en línea recta a una cámara llamada la cámara delantera. Los túneles no se intersectan (ellos solamente se encuentran en las cámaras). Dos cámaras pueden estar conectadas con un túnel simple, o no estar conectadas enteramente (esto, no obstante, puede ser posible alcanzar una cámara desde otra vía las cámaras restantes). Un túnel siempre conecta dos cámaras distintas.

Se ha decidido que se organice la competición llamada 'Copa Byteotia del Rey'. El objetivo de cada competidor es recorrer una ruta elegida libremente en la cueva y salir tan rápido como sea posible. La ruta tiene que dirigirse a través de al menos una de las otras cámaras que no sea la cámara delantera. Solamente dos reglas están vigentes: durante el viaje a través de la cueva cada cámara (con excepción de la cámara delantera) pueden ser visitadas una vez a lo sumo, de manera similar cada pasillo no puede ser atravesado más de una vez.

Byteala un famoso explorador de cuevas se está  preparando para la competición. Byteala ha estado entrenando en la cueva por un largo tiempo y él ha adquirido un conocimiento detallado del sistema de pasillos de la cueva. Para cada pasillo él ha calculado la cantidad de tiempo necesario para atravesarlo en cada dirección. El tiempo para moverse dentro de una cámara puede ser desechado. Ahora a Byteala le gustaría calcular una ruta que satisfaga los requerimientos de la competencia, la cual puede ser recorrida en el menor tiempo posible (el tiempo necesario para recorrer una ruta es la suma de los tiempos necesitados para atravesar los pasillos de los cuales esta consiste).

Escriba un programa el cual:

• lea desde la entrada una descripción de la cueva y los tiempos necesarios para atravesar cada pasillo,
• calcule una ruta consecuente con los requerimientos, para la cual la suma de los tiempos necesitados para atravesar los pasillos sea mínima,
• escriba hacia la salida el tiempo requerido para recorrer la ruta calculada.

Entrada

En la primera línea de la entrada hay dos enteros ~N~ y ~M~ ~(3 \le N \le 5000,3 \le M \le 10000)~ separadas por un espacio denotando el número de cámaras en la cueva y el número de pasillos entrelazados, respectivamente. Las cámaras están numeradas desde ~1~ hasta ~N~. La cámara delantera está  denotada por ~1~. Las siguientes M líneas contienen una descripción de los pasillos. En cada una de estas líneas hay cuatro enteros separados por un espacio simple. Un cuatro-tuplo ~a,b,c,d~ significa que las cámaras ~a~ y ~b~ están conectadas por un pasillo, el tiempo para atravesar de ~a~ hasta ~b~ es ~c~ y de ~b~ hasta ~a~ es ~d~, \(1 \le a,b \le n, a ≠ b, 1 \le c,d \le 10000\). Usted puede asumir que una ruta que satisfaga los requerimientos de la competición siempre va a existir.

Salida

Su programa debe escribir en la primera y única línea de la salida un entero - el tiempo mínimo requerido para recorrer una ruta que satisfaga las condiciones de la competencia.

Ejemplo de entrada

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

Ejemplo de salida

6