폭염

텍사스에 올여름 폭염이 찾아왔습니다. Farmer John은 사람들이 더위를 견딜 수 있도록 위스콘신에서 텍사스까지 시원한 우유를 넉넉히 배달하는 일을 맡았습니다.

우유를 옮길 수 있는 경로에는 출발 마을과 도착 마을을 포함해 총 $T$개의 마을이 있으며, $1$부터 $T$까지 번호가 매겨져 있습니다. 각 도로는 두 마을을 양방향으로 잇고, 통행에 드는 비용(연료, 통행료 등)이 정해져 있습니다.

아래는 마을 7개로 이루어진 지도의 예시입니다. 마을 $5$가 우유의 출발지, 마을 $4$가 도착지이며, 대괄호 안의 숫자는 각 도로의 통행 비용을 나타냅니다.

                              [1]----1---[3]-
                             /               \
                      [3]---6---[4]---3--[3]--4
                     /               /       /|
                    5         --[3]--  --[2]- |
                     \       /        /       |
                      [5]---7---[2]--2---[3]---
                            |       /
                           [1]------

예를 들어 $5 \to 6 \to 3 \to 4$ 경로로 이동하면 $3 + 4 + 3 = 10$의 비용이 듭니다.

총 $C$개의 도로 정보(각 도로는 양 끝 마을 $R1_i$, $R2_i$와 비용 $C_i$로 표현됩니다)가 주어질 때, 출발 마을 $T_s$에서 도착 마을 $T_e$까지 이동하는 데 드는 최소 총 비용을 구하세요.

제약 조건: $1 \le T \le 2500$, $1 \le C \le 6200$, $1 \le R1_i, R2_i \le T$, $1 \le C_i \le 1000$, $1 \le T_s, T_e \le T$.

• 첫째 줄: 공백으로 구분된 네 정수 $T$, $C$, $T_s$, $T_e$.
• $2$번째 줄부터 $C+1$번째 줄까지: $i$번째 도로를 나타내는 세 정수 $R1_i$, $R2_i$, $C_i$가 공백으로 구분되어 주어집니다.

• 첫째 줄: $T_s$에서 $T_e$까지 가는 최단 경로의 총 비용을 나타내는 정수 하나를 출력합니다. 적어도 하나의 경로가 반드시 존재합니다.

위 입력 예시에서 최단 경로는 $5 \to 6 \to 1 \to 4$이며, 비용은 $3 + 1 + 3 = 7$입니다.