지름길

매일 저녁, Farmer John은 거대한 종을 울려 소들을 저녁 식사를 위해 헛간으로 불러 모은다. 소들은 최대한 빨리 헛간에 도착하고 싶어 하므로, 모두 헛간까지의 최단 경로를 따라 이동한다.

농장은 $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번 들판을 지나는 경로보다 선호된다.

Farmer John은 헛간이 일부 들판에서 멀리 떨어져 있는 것을 걱정한다. 그는 모든 소에 대해 각 소가 겪는 이동 시간을 더한 값을 총 이동 시간이라고 부른다. 그는 헛간(1번 들판)에서 원하는 다른 들판으로 이동 시간 $T$인 지름길을 하나 추가하여 이 값을 최대한 줄이고 싶어 한다($1 \leq T \leq 10,000$). 소가 평소 헛간으로 가는 경로를 따라가다가 지름길을 발견하면, 지름길을 이용하는 편이 헛간에 더 빨리 도착할 수 있을 때만 지름길을 택한다. 그렇지 않으면 지름길을 이용해 이동 시간을 줄일 수 있더라도 평소 경로를 따른다.

Farmer John이 지름길을 추가하여 얻을 수 있는 총 이동 시간의 최대 감소량을 구하시오.

첫 번째 줄에는 $N$, $M$, $T$가 주어진다. 다음 줄에는 $N$개의 정수 $c\_1 \ldots c\_N$이 주어지며, 각 값은 $0 \ldots 10,000$ 범위에 있다. 다음 $M$개의 줄에는 각각 길을 나타내는 세 정수 $a$, $b$, $t$가 주어지며, 이는 $a$번 들판과 $b$번 들판을 연결하는 길의 이동 시간이 $t$라는 뜻이다. 모든 이동 시간은 $1 \ldots 25,000$ 범위에 있다.

Farmer John이 얻을 수 있는 총 이동 시간의 최대 감소량을 출력하시오.