Zur Fitness laufen $N$ Kühe ($(2 \le N \le 1,000,000)$) eine Staffel auf den $T$ Wegen ($(2 \le T \le 100)$) der Weide.

Jeder Weg verbindet zwei verschiedene Kreuzungen ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), jede mit mindestens zwei Wegen. Länge $length_i$ ($(1 \le length_{i} \le 1,000)$) und Enden bekannt; kein Paar hat zwei direkte Wege. Ein mathematischer Graph.

Die $N$ Kühe stehen an Kreuzungen, auch mehrere an derselben. Richtige Aufstellung ermöglicht Staffelstabübergabe Kuh für Kuh bis zum Ziel.

Hilf mit dem kürzesten Weg von Start $S$ zu Ende $E$ über genau $N$ Wege.

Eingabe

• Zeile $1$: getrennte ganze Zahlen $N$, $T$, $S$, $E$.

• Zeilen $2..T+1$: Zeile $i+1$ beschreibt Weg $i$ mit $length_i$, $I1_i$, $I2_i$ getrennt.

Ausgabe

• Zeile $1$: eine ganze Zahl, kürzeste Entfernung $S$ zu $E$ über genau $N$ Wege.

Beispiele

Eingabe 1

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

Ausgabe 1

10

Aufgabenautor: Erik Bernhardsson, 2003