為鍛鍊，$N$ 頭牛（$(2 \le N \le 1,000,000)$）利用牧場 $T$ 條路（$(2 \le T \le 100)$）跑接力。

各路連兩不同路口（$(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$），每口至少連兩路。已知長 $length_i$（$(1 \le length_{i} \le 1,000)$）與兩端，沒有兩路直接連同一對口。道路是數學的圖。

$N$ 頭牛站各路口，口可多頭。須合理站位，逐牛傳棒到正確終點。

求起點 $S$ 到終點 $E$ 恰經 $N$ 路的最短路徑，幫助安排。

輸入格式

• 第 $1$ 行：空格分隔整數 $N$、$T$、$S$、$E$。

• 第 $2..T+1$ 行：第 $i+1$ 行給路 $i$ 三個空格分隔整數 $length_i$、$I1_i$、$I2_i$。

輸出格式

• 第 $1$ 行：$S$ 到 $E$ 恰過 $N$ 路最短距離，一整數。

範例

輸入格式 1

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

輸出格式 1

10

出題者：Erik Bernhardsson，2003