Para ejercitarse, $N$ vacas ($(2 \le N \le 1,000,000)$) corren relevos en los $T$ senderos ($(2 \le T \le 100)$) del prado.

Cada sendero une dos cruces distintos ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), cada uno toca al menos dos senderos. Longitud $length_i$ ($(1 \le length_{i} \le 1,000)$) y extremos conocidos; no dos senderos directos entre una pareja. Es un grafo matemático.

Las $N$ vacas se colocan en cruces, varios animales pueden compartir uno. Deben pasar el testigo vaca a vaca hasta la meta correcta.

Ayuda a colocarlas: camino mínimo entre $S$ y $E$ con exactamente $N$ senderos.

Entrada

• Línea $1$: enteros $N$, $T$, $S$, $E$ separados.

• Líneas $2..T+1$: línea $i+1$ describe sendero $i$ con $length_i$, $I1_i$, $I2_i$ separados.

Salida

• Línea $1$: un entero, distancia mínima $S$ a $E$ por exactamente $N$ senderos.

Ejemplos

Entrada 1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

Salida 1

10

Autor del problema: Erik Bernhardsson, 2003