레이팅 미적용매일 저녁 농부 존은 거대한 종을 울려 소들을 저녁 식사를 위해 헛간으로 불러 모은다. 소들은 최대한 빨리 헛간에 가고 싶어서 모두 가능한 가장 짧은 경로를 따라 이동한다.
농장은 \(N\)개의 밭 (\(1 \leq N \leq 10,000\))으로 이루어져 있으며, 편의상 \(1 \ldots N\)번으로 번호가 매겨져 있고, 헛간은 밭 1에 있다. 밭들은 \(M\)개의 양방향 오솔길 (\(N-1 \leq M \leq 50,000\))로 연결되어 있다. 각 오솔길에는 이동 시간이 정해져 있으며, 모든 밭에서 오솔길들을 통해 헛간까지 가는 경로가 존재한다.
밭 \(i\)에는 \(c_i\)마리의 소가 있다. 저녁 종소리를 들으면 이 소들은 모두 걸리는 시간이 최소인 경로를 따라 헛간까지 걸어간다. 시간이 최소인 경로가 여러 개라면, 소들은 그중 "사전순"으로 가장 작은 경로를 택한다 (즉, 두 경로 사이의 동점은 경로가 처음으로 달라지는 지점에서 번호가 더 작은 밭을 사용하는 쪽을 선호하는 것으로 해소한다. 예를 들어 밭 7, 3, 6, 1을 지나는 경로와 7, 5, 1을 지나는 경로의 이동 시간이 같다면 앞의 경로가 선호된다).
농부 존은 일부 밭이 헛간에서 멀리 떨어져 있는 것이 걱정이다. 그는 모든 소가 겪는 이동 시간을 전부 더한 값을 총 이동 시간이라고 부른다. 그는 이동 시간이 \(T\) (\(1 \leq T \leq 10,000\))인 여분의 "지름길" 오솔길 하나를 헛간 (밭 1)에서 자신이 고른 어떤 밭까지 추가하여, 이 수를 가능한 한 많이 줄이고 싶어한다. 소가 헛간으로 가는 평소 경로를 따라 이동하다가 지름길 오솔길을 마주치면, 그 길이 헛간까지 더 빨리 데려다줄 경우에 그 길을 이용한다. 그렇지 않으면 지름길을 이용해 이동 시간을 줄일 수 있었더라도 평소 경로를 그대로 따른다.
지름길 오솔길을 추가하여 농부 존이 달성할 수 있는 총 이동 시간 감소량의 최댓값을 구하도록 도와주자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\), \(M\), \(T\)가 주어진다. 다음 줄에 \(N\)개의 정수 \(c_1 \ldots c_N\)이 주어지며, 각각 \(0 \ldots 10,000\) 범위이다. 다음 \(M\)개의 줄에는 각각 오솔길 하나를 나타내는 세 정수 \(a\), \(b\), \(t\)가 주어지며, 이는 그 오솔길이 밭 \(a\)와 \(b\)를 연결하고 이동 시간이 \(t\)임을 나타낸다. 모든 이동 시간은 \(1 \ldots 25,000\) 범위이다.
농부 존이 달성할 수 있는 총 이동 시간 감소량의 최댓값을 출력한다.
shortcut.in · 출력을 쓸 파일 shortcut.out5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 740