물자 조달

시간 제한1초메모리 제한1024 MB

요약

부대에 들어갈 때 검문시간이 드는 그래프에서, 검문시간이 단조 증가하고 각 부대가 한 번만 공격받는다는 조건 아래 최단 시간을 갱신하며 질의에 답한다.

문제

현재 A국과 B국 두 나라는 서로 전쟁 중이다. A국의 운전병 해찬이는 조국의 승리를 위해 출발 부대에서 도착 부대로 물자를 조달하는 임무를 맡았다.

A국에는 $1$ 부터 $N$ 까지 번호가 매겨진 $N$ 개의 부대가 존재하며 각 부대는 도로로 연결되어 있다. 또한, 각 도로를 지나갈 때는 일정한 시간이 소요된다.

각 부대들은 보안을 위해 들어오는 차량을 검문하며, 이때 검문시간 $t\_i$ 가 소요된다. 다만 출발 부대와 도착 부대에는 미리 공문이 내려가 있기 때문에 검문시간이 소요되지 않는다.

B국은 A국의 각 부대를 목표로 삼아 습격하며 이때 습격받은 부대는 보안이 강화되어 검문시간이 증가한다. 또한 B국은 한 번 공격 목표가 다른 부대로 바뀌면 이후 이전에 목표로 삼았던 부대들은 다시 공격하지 않는다.

다음과 같은 $Q$ 개의 쿼리가 주어질 때 해찬이를 도와 A국의 승리를 도와주자.

첫 번째 줄에 부대의 수 $N$ , 도로의 수 $M$ , 쿼리의 수 $Q$ 가 공백으로 구분되어 주어진다.

두 번째 줄에 각 부대의 검문시간을 의미하는 $N$ 개의 정수 $t\_1, \cdots, t\_N$ 이 공백으로 구분되어 주어진다.

이후 $M$ 개의 줄에 걸쳐 $u,v,w$ 가 공백으로 구분되어 주어지며 이는 $u$ 번 부대에서 $v$ 번 부대로 가는데 $w$ 만큼의 시간이 걸리는 양방향 도로가 존재한다는 뜻이다.

이후 $Q$ 개의 줄에 걸쳐 다음과 같은 두 가지 종류의 쿼리가 한 줄에 하나씩 주어진다.

주어진 2번 쿼리의 출력값을 한 줄에 하나씩 출력한다.

예제 1

입력

예상 출력

6
7

예제 2

입력

예상 출력

8
-1