Para se exercitar, $N$ vacas ($(2 \le N \le 1,000,000)$) correm revezamento nas $T$ trilhas ($(2 \le T \le 100)$) do pasto.

Cada trilha une dois cruzamentos distintos ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), cada um toca ao menos duas trilhas. Comprimento $length_i$ ($(1 \le length_{i} \le 1,000)$) e extremos conhecidos; não há duas trilhas diretas entre um par. É grafo matemático.

As $N$ vacas se colocam nos cruzamentos, várias podem compartilhar um. Devem passar o bastão vaca a vaca até a chegada correta.

Ajude a posicioná-las: caminho mínimo entre $S$ e $E$ com exatamente $N$ trilhas.

Entrada

• Linha $1$: inteiros $N$, $T$, $S$, $E$ separados.

• Linhas $2..T+1$: linha $i+1$ descreve trilha $i$ com $length_i$, $I1_i$, $I2_i$ separados.

Saída

• Linha $1$: um inteiro, distância mínima $S$ a $E$ por exatamente $N$ trilhas.

Exemplos

Entrada 1

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

Saída 1

10

Autor do problema: Erik Bernhardsson, 2003