시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 32 14 14 43.750%

문제

20XX년에 IOI나라에서 열리는 올림픽 준비의 일환으로 IOI나라에 있는 JOI공원을 정비하기로 했다. JOI공원에는 N개의 광장이 있고, 1부터 N까지 번호가 붙어 있다. 또, 공원에는 광장을 연결하는 M개의 도로가 있고, 1부터 M까지 번호가 붙어있다. 도로 i (1 ≦ i ≦ M)는 광장 Ai와 광장 Bi를 쌍방향으로 연결하며 그 길이는 Di이다. 어떤 광장에서도 한 개 이상의 도로를 통해서 다른 광장으로 가는 것이 가능하다.

정비계획은 다음과 같다. 지하도 설치에 관한 변수 C가 주어진다. 먼저, 0 이상의 정수 X를 고르고 광장 1로부터 거리가 X이하인 광장(광장 1을 포함해서) 모두를 지하도로 연결한다. 단, 광장 i와 광장 j의 거리는 광장 i로부터 광장 j까지 가는 데 걸리는 도로의 길이의 최소로 정의한다. 지하도를 설치하는 데에 드는 전체 비용은 C × X이다.

다음으로, 지하도로 연결된 광장들을 잇는 도로를 전부 철거한다. 도로를 철거하는 데에 비용은 들지 않는다.

마지막으로, 철거되지 않고 남은 도로를 전부 보수한다. 길이 d의 도로를 보수하는데에 드는 비용은 d이다.

정비계획을 실시하기 전, JOI공원에 지하도는 없다. JOI공원에 있는 광장의 정보와 지하도 설치 비용이 주어질 때, JOI공원을 정비하는 데에 드는 비용의 최소값을 구하는 프로그램을 작성하여라.

입력

표준입력으로 다음의 정보가 주어진다.

  • 첫 번째 줄에는 정수 N,M,C가 공백을 두고 주어진다. 이것은 광장이 N개, 도로가 M개 있고, 지하도 설치에 관한 변수가 C라는 것을 의미한다.
  • 다음 M개 행에서는 정수 Ai,Bi,Di (1 ≦ i ≦ M) 가 공백을 두고 한 줄씩 주어진다. 이것은 도로 i가 광장 Ai와 Bi를 잇고, 그 길이가 Di라는 것을 의미한다.
모든 입력 데이터는 아래의 조건을 만족한다.
  • 2 ≦ N ≦ 100 000.
  • 1 ≦ M ≦ 200 000.
  • 1 ≦ C ≦ 100 000.
  • 1 ≦ Ai ≦ N (1 ≦ i ≦ M).
  • 1 ≦ Bi ≦ N (1 ≦ i ≦ M).
  • Ai ≠ Bi (1 ≦ i ≦ M).
  • (Ai, Bi) ≠ (Aj, Bj) 및 (Ai, Bi) ≠ (Bj, Aj) (1 ≦ i < j ≦ M).
  • 1 ≦ Di ≦ 100 000 (1 ≦ i ≦ M).
  • 주어지는 입력 데이터에 대해서는 어떤 광장에서도 한 개 이상의 도로를 통해서 다른 광장으로 갈 수 있는 것이 보증된다.

출력

JOI공원 정비에 드는 비용의 최대값을 1줄로 출력한다.

예제 입력

5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5

예제 출력

14

예제 입력 2

5 4 10
1 2 3
2 3 4
3 4 3
4 5 5

예제 출력 2

15

예제 입력 3

6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5

예제 출력 3

10

힌트

이 입력예제에서는 X = 3으로 하여 광장 1로부터 거리가 3이하가 되는 광장(광장 1, 광장 2, 광장 3)을 전부 지하도로 이었을 경우, 정비하는 데에 드는 비용의 합은 (2 × 3) + (3 + 5) = 14이다. 이것이 최소값이다.

출처

Olympiad > 일본정보올림피아드 > JOI 2015 3번