Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Para el examen físico de este año, el profesor de deporte de Fito ha decidido que sus estudiantes deben correr por exactamente N (2 <= N <= 1000000) senderos, ni más ni menos. Como N puede ser demasiado grande, el profesor ha decidido que sus alumnos escojan la ruta que ellos deseen, pero siempre se deben recorrer N senderos. Fito se da cuenta que sufrirá inevitablemente pero siendo un alumno muy inteligente decide buscar la ruta que minimice la distancia recorrida. En el campo de educación física existen 1000 intersecciones (numeradas de 1  a 1000) y T (2 <= T <= 100) senderos. Cada sendero tiene longitud positiva menor que 1000 unidades y conecta dos intersecciones diferentes. El profesor ha señalado dos intersecciones S y E que serán la de inicio y final del recorrido respectivamente.

Input

Línea 1 : Cuatro enteros separados por espacios: N, T, S y E.
Líneas 2... T+1 : La línea i describe el sendero i con tres enteros separados por espacios: longitud,  intersección #1 e intersección  #2.

Output

Línea 1: Un solo entero que es la distancia más corta de la intersección S a la intersección E que recorra exactamente N senderos.

Sample test(s)