시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 94 30 15 62.500%

문제

자랑스러운 대한민국의 산업기능Agent 욱제는 집 떠나와 열차 타고 훈련소로 떠난다.

모두 알다시피 대한민국은 정점이 V개이고 간선이 E개인 선인장 그래프이고, 집은 1번 정점, 훈련소는 V번 정점이다.

하지만 욱제는 Agent를 감히 훈련소로 보내는 대한민국에 환멸을 느끼고, 간선 몇 개에 수류탄을 떨어뜨리기로 한다. 수류탄으로 간선을 터뜨리면 그 간선을 타고 이동할 수 없게 된다.

욱제는 간선 몇 개를 터뜨린 다음 집에서 훈련소로 가는 경로가 없게 하고 싶다. 4월 2일이 오기 전에 빨리, 욱제가 터뜨려야 할 간선의 길이의 합의 최솟값을 구하자.

입력

첫째 줄에 V, E가 주어진다.

둘째 줄부터 E개의 줄에 대한민국을 이루는 그래프의 각 간선이 잇고 있는 두 정점의 번호 x, y와 간선의 길이 d가 공백을 사이에 두고 주어진다.

출력

욱제가 터뜨려야 하는 간선의 길이의 합의 최솟값을 출력한다. 간선을 어떻게 터뜨려도 훈련소로 가는 경로가 존재하면, 권욱제 재입대를 출력한다.

제한

  • 2 ≤ V ≤ 402,000
  • V - 1 ≤ E ≤ 429,000
  • 1 ≤ x, y ≤ V 
  • 1 ≤ d ≤ 19,990,316
  • 주어지는 그래프는 무방향 단순 연결 그래프이다.
  • 주어지는 그래프는 선인장 그래프이다. 즉, 한 간선이 두 개 이상의 사이클에 포함되지 않는다.

예제 입력 1

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

예제 출력 1

3

2번 정점과 3번 정점을 잇고 있는 길이 1의 간선과, 5번 정점과 1번 정점을 잇고 있는 길이 2의 간선을 하나씩 터뜨린다. 그러면 집(1번 정점)에서 훈련소(6번 정점)으로 가는 경로가 없어진다.

출처

Contest > 논산 코드 페스티벌 > 제1회 논산 코드 페스티벌 A번

  • 문제를 만든 사람: junie
  • 데이터를 추가한 사람: Lawali