물자 조달 | cho.sh

현재 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번 쿼리의 출력값을 한 줄에 하나씩 출력한다.