체력 훈련을 위해 $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