정확히 N개 길을 지나는 릴레이

체력 훈련을 위해 N (2 <= N <= 1,000,000)마리의 소가 목장의 T (2 <= T <= 100)개 길을 이용해 릴레이를 하려고 한다.

각 길은 서로 다른 두 교차점을 잇는다. 교차점 번호는 1 이상 1,000 이하이며, 등장하는 모든 교차점에는 적어도 두 개의 길이 연결되어 있다. 각 길에 대해 길이 (1 <= length_i <= 1,000)와 그 길이 잇는 두 교차점 I1_i, I2_i가 주어진다. 같은 두 교차점을 직접 잇는 길이 두 개 이상 주어지지는 않는다.

소들은 여러 교차점에 설 수 있고, 같은 교차점에 여러 마리가 서도 된다. 바통이 소에서 소로 차례대로 전달되어야 하며, 전체 이동은 시작 교차점 S에서 출발해 끝 교차점 E에 도착하고 정확히 N개의 길을 지나야 한다.

이 조건을 만족하는 이동 경로의 가능한 최소 총거리를 구하라.

• 첫째 줄: 공백으로 구분된 네 정수 N, T, S, E가 주어진다.
• 둘째 줄부터 T+1번째 줄까지: i+1번째 줄에는 i번째 길을 나타내는 세 정수 length_i, I1_i, I2_i가 공백으로 구분되어 주어진다.

교차점 S에서 교차점 E까지 정확히 N개의 길을 지날 때의 최단 거리를 나타내는 정수 하나를 출력한다.