Matcom Online Grader

Fito está entrenando para un maratón. Detrás de su casa hay un parque con una red muy grande de senderos que conectan estaciones de agua. Fito quiere encontrar la ruta más corta que use cada sendero por lo menos una vez.

Input

La entrada contiene varios casos de prueba. La primera línea por cada caso de prueba son dos enteros positivos: n < = 15, el número de estaciones de agua, y m < 1000, el número de senderos. Por cada sendero hay una línea. Esa línea tiene 3 enteros positivos, los primeros dos entre 1 y n, indicando las fuentes de inicio y de fin del sendero, el tercer entero es la longitud del sendero.

Puede haber más de un sendero entre cualquier dos estaciones; cada sendero diferente es dado solamente una vez en la entrada, cada sendero puede ser viajado en cualquier dirección. Es posible alcanzar cualquier sendero de cualquier otro sendero visitando una secuencia de estaciones de agua conectadas por senderos. La ruta de Fito puede empezar en cualquier estación de agua, y debe terminar en la misma estación. Una línea sola que contiene 0 define la última prueba.

Output

Para cada caso de prueba, debe haber una línea con la longitud mínima de la ruta encontrada.

Sample test(s)