Stysti Skógarleiðangurinn

이미지 출처: leagueoflegends.fandom.com

Arnar와 Sammi는 열성적인 League of Legends 플레이어이며, 이 게임을 한동안 플레이해 왔다. 많은 사람이 믿지 않지만, League of Legends는 팀 게임이므로 팀원을 돕는 것이 매우 중요하다. Sammi는 정글러 역할을 맡으며, 팀을 도울 때 가장 중요한 임무를 수행한다. 정글러의 목표는 정글 몬스터를 처치하고 팀원들의 공격로를 방문하여 적 플레이어들을 본진으로 돌려보내는 것이다. 반면 Arnar는 Attack Damage Carry이며, 적들을 본진으로 돌려보내는 것을 무엇보다 좋아한다. 그래서 그는 Sammi에게 가능한 한 빨리 자신이 있는 곳으로 와 달라고 부탁한다. 하지만 Sammi에게는 다른 우선순위가 있다. 그는 어느 공격로든 방문하기 전에 모든 정글 몬스터를 처치하는 것을 선호한다. 그러나 팀원들이 너무 오래 기다리게 하고 싶지는 않으므로, 그는 항상 모든 정글 몬스터를 처치할 수 있는 가장 빠른 경로를 택한다.

게임 개발자들이 정글 경로를 바꾸기 시작하면서 이 과정은 더 어려워졌고, 그 때문에 Arnar는 Sammi가 정글의 모든 몬스터를 처치하는 데 얼마나 오래 걸릴지 전혀 알 수 없다. 지금 Sammi는 모든 정글 몬스터를 처치하느라 너무 바쁘고, Arnar는 자신의 본진으로 돌아가지 않기 위해 분투하느라 바쁘다. 따라서 Arnar는 Sammi가 모든 정글 몬스터를 처치하는 데 얼마나 걸릴지 알아내도록 도와 달라고 부탁한다. 그래야 Sammi가 자신을 도우러 올 때까지 얼마나 기다려야 하는지 알 수 있기 때문이다.

Sammi는 항상 첫 정글 몬스터를 처치할 때 도움을 받으므로 언제나 같은 장소에서 시작한다. 또한 Sammi는 때때로 소환사 주문인 강타를 사용할 수 있다. Sammi가 정글 몬스터에게 강타를 사용하면 그 몬스터를 즉시 처치하므로, 일반 능력으로 처치하기 위해 멈출 필요가 없다.

채점

그룹 | 점수 | 제약 조건

1 | 15 | $n = 1$, $0 \leq s \leq 1$

2 | 15 | $n = 2$, $0 \leq s \leq 2$

3 | 20 | $1 \leq n \leq 8$, $s = 0$

4 | 20 | $1 \leq n \leq 8$, $1 \leq s \leq n$

5 | 15 | $1 \leq n \leq 16$, $s = 0$

6 | 15 | $1 \leq n \leq 16$, $1 \leq s \leq n$

입력의 첫째 줄에는 세 정수 $n, m$와 $s$가 주어진다. 여기서 $n$은 정글 몬스터의 수, $m$는 경로의 수, 그리고 $s$는 Sammi가 사용할 수 있는 강타의 수이다. 다음 줄에는 $n$개의 정수가 주어지며, 각 정수 $1 \leq x_i \leq 10^4$는 번호가 $i$인 몬스터를 처치하는 데 걸리는 시간이다. 마지막으로 $m$개의 줄이 주어지며, 각 줄에는 세 정수 $u, v$와 $t$가 주어진다. 이는 몬스터 $u$와 몬스터 $v$ 사이에 이동하는 데 $1\leq t \leq 10^4$만큼의 시간이 걸리는 경로가 있다는 뜻이다.

Sammi가 번호가 $1$인 몬스터에서 시작할 때, 모든 정글 몬스터를 처치하는 데 걸리는 최단 시간을 출력한다.