시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB298655728.358%

문제

??? : 자 얘들아 이건 다이제스타 쓰면 돼, 다이제스타.

준혁 : 다이제스타가 뭐야? (검색한다)

준혁 : 아하! 다이제는 과자 이름이구나. 그럼 스타는 뭐지?

진호 : 스타크래프트 좋아하시잖아~

스타크래프트의 저그들은 커널을 가지고 있다. 커널은 1부터 $N$까지 번호가 붙어 있으며 커널들은 길이가 있는 양방향 연결통로를 통해 연결되어 있다.

저그들은 이 연결통로를 이용하여 시작 커널부터 끝 커널까지 자신들의 주식인 다이제를 운반한다. 저그들은 다이제를 운반할때 항상 전에 이동했던 연결통로보다 더 길이가 긴 연결통로를 이용해야만 한다. 그리고 이러한 이동방법 중 총 이동 거리가 가장 짧은 경로를 이용한다. 만약 한번도 연결통로를 이용한 적이 없다면, 아무 연결통로나 이용 할 수 있다.

저그들은 이 이동 방법을 다이제스타라고 부르기로 했다.

준혁이와 진호는 다이제스타가 어떤 방식으로 이루어지는지 궁금해졌다. 준혁이와 진호를 위해 다이제스타를 구현해보자.

입력

첫째 줄에 커널의 개수 $N$과 연결통로의 개수 $M$가 주어진다. $(1 ≤ N ≤ 50,000, 1 ≤ M ≤ 100,000)$

두번째 줄부터 $M$개의 줄에 연결통로를 통해 연결되어 있는 두 커널과 연결통로의 길이가 주어진다. 연결통로의 길이는 $10^7$보다 작거나 같은 양의 정수이다.

입력의 마지막 줄에는 시작 커널의 번호와 끝 커널의 번호가 입력된다.

출력

첫째 줄에 운반을 완료했을 때 저그들의 총 이동 거리를 출력해라. 만약 저그들이 커널을 통해 운반을 완료하는 것이 불가능할 경우 DIGESTA를 출력해야 한다.

서브태스크

번호배점제한
17

$M = N-1$이고, 1번 커널과 2번 커널, 2번 커널과 3번 커널, … $N-1$번 커널과 $N$번 커널을 연결하는 연결통로만 존재한다.

229

$N ≤ 5,000$, $M ≤ 6,000$

364

추가제약조건이 없다.

예제 입력 1

7 8
1 2 8
1 5 4
1 6 4
2 3 9
2 4 6
4 5 5
4 6 3
4 7 8
1 7

예제 출력 1

17

1번, 5번, 4번, 7번 커널 순서대로 하면 4 + 5 + 8 = 17 만큼 이동하므로 17이 답이 된다.

1번, 6번, 4번, 7번 커널 순서대로 할 경우에는 4 + 3 + 8 = 15로 이동거리는 17보다 작지만 1번 커널에서 6번 커널로 갈때보다 6번 커널에서 4번 커널로 갈때 거리가 더 짧아서 불가능하다. 

예제 입력 2

8 10
1 2 5
1 3 7
2 4 6
3 5 5
3 8 6
4 7 8
5 8 9
5 7 10
6 7 4
7 8 7
2 8

예제 출력 2

DIGESTA

채점 및 기타 정보

  • 예제는 채점하지 않는다.