Per allenarsi, $N$ mucche ($(2 \le N \le 1,000,000)$) corrono una staffetta sui $T$ sentieri ($(2 \le T \le 100)$) del prato.

Ogni sentiero collega due incroci distinti ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), ciascuno tocca almeno due sentieri. Lunghezza $length_i$ ($(1 \le length_{i} \le 1,000)$) e estremi noti; nessun doppio sentiero diretto fra una coppia. Un grafo matematico.

Le $N$ mucche si posizionano agli incroci, anche più allo stesso. Devono passare il testimone mucca per mucca fino alla giusta meta.

Aiuta a posizionarle: percorso minimo fra $S$ e $E$ con esattamente $N$ sentieri.

Input

• Riga $1$: interi $N$, $T$, $S$, $E$ separati.

• Righe $2..T+1$: riga $i+1$ descrive sentiero $i$ con $length_i$, $I1_i$, $I2_i$ separati.

Output

• Riga $1$: un intero, distanza minima $S$ a $E$ per esattamente $N$ sentieri.

Esempi

Input 1

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

Output 1

10

Autore del problema: Erik Bernhardsson, 2003