시장 속 지름길

매일 저녁, 시장 관리인은 스피커를 통해 이벤트 방송을 합니다. 이벤트에 빨리 참여하고 싶은 사람들은 그 방송을 듣기 위해 스피커가 있는 부스로 최단 경로를 따라 도착합니다.

시장은 $N$개의 부스 ($1 \leq N \leq 10,000$)로 구성되어 있으며 부스들은 $1 \ldots N$로 번호가 매겨져 있습니다. 중앙 스피커는 1번 부스에 위치해 있습니다. 사람들이 이동할 수 있는 부스는 $M$ 양방향 집합($N-1 \leq M \leq 50,000$)으로 연결됩니다. 각 경로에는 이동 시간이 있으며, 모든 필드에서 일부 경로 집합을 사용하여 1번 부스로 이동할 수 있는 경로가 있습니다.

$i$번째 부스에는 $c_i$명의 사람들이 있습니다. 방송 소리가 들리면 이 사람들은 모두 최소 시간이 걸리는 경로를 따라 1번 부스로 걸어갑니다. 최소 시간이 같은 경로가 여러 개 있는 경우, 사람들은 이 중 '사전적으로' 가장 작은 경로를 택합니다. (e.g. 7,3,6,1을 방문하는 경로가 7,5,1을 방문하는 경로보다 더 낫습니다.)

모든 사람들의 이동 시간을 합산하여 '총 이동 시간'이라고 부르는데, 시장 관리인은 중앙 스피커가 있는 1번째 부스에서 자신이 생각하기에 너무 멀리 떨어져있는 다른 부스까지의 '지름길' 을 추가하려고 합니다. 원래 $T$($1 \leq T \leq 10,000$)보다 많이 걸리던 거리에 '지름길'을 추가하게 된다면 걸리는 시간이 T로 단축 됩니다. 이렇게 지름길을 추가함으로써 다른 사람들은 더욱 빠르게 중앙 스피커가 있는 부스로 달려갈 수 있습니다.

시장 관리인이 지름길을 추가함으로써 얻을 수 있는 총 이동 시간 감소의 최대 감소 값을 계산해주세요.

입력의 첫 번째 줄에는 $N$, $M$, 그리고 $T$가 주어집니다. 그 다음 줄에는 $N$개의 정수 $c_1 \ldots c_N$이 주어지며, 각각은 $0 \ldots 10,000$의 범위에 있습니다. 그 다음 $M$ 줄에는 각각 $a$, $b$, $t$ 세 개의 정수로 각 길을 나타냅니다. 길은 부스 $a$와 $b$를 연결하고 거리(시간)은 $t$입니다. 모든 거리(시간)는 $1 \ldots 25,000$ 범위에 있습니다.

시장 관리인이 얻을 수 있는 총 이동 시간 감소의 최대치를 출력하세요