물자 조달

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

A국에는 $1$부터 $N$까지 번호가 매겨진 $N$개의 부대가 있으며, 각 부대는 도로로 연결되어 있다. 각 도로를 지나는 데는 일정한 시간이 걸린다.

각 부대는 보안을 위해 들어오는 차량을 검문한다. 부대 $i$에서 검문하는 데 $t_i$의 시간이 걸린다. 다만 출발 부대와 도착 부대에는 미리 공문이 내려가 있어서 검문 시간이 걸리지 않는다.

B국은 A국의 부대를 하나씩 목표로 삼아 습격한다. 습격을 받은 부대는 보안이 강화되어 검문 시간이 늘어난다. B국이 공격 목표를 다른 부대로 바꾸면, 이전에 목표였던 부대는 다시 공격하지 않는다.

다음과 같은 $Q$개의 쿼리에 답하여 해찬이를 도와 A국의 승리를 이끌자.

• $1$ $r$ $c$: B국이 $r$번 부대를 공격하여 $r$번 부대의 검문 시간이 $c$만큼 늘어난다.
• $2$ $a$ $b$: $a$번 부대에서 $b$번 부대까지 가는 최소 시간을 출력한다. 도달할 수 없으면 -1을 출력한다.

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

두 번째 줄에 각 부대의 검문 시간을 나타내는 $N$개의 정수 $t_1, \cdots, t_N$이 공백으로 구분되어 주어진다.

이후 $M$개의 줄에 $u$, $v$, $w$가 공백으로 구분되어 주어진다. 이는 $u$번 부대와 $v$번 부대 사이에 $w$의 시간이 걸리는 양방향 도로가 있다는 뜻이다.

마지막 $Q$개의 줄에는 위에서 설명한 두 종류의 쿼리가 한 줄에 하나씩 주어진다.

2번 쿼리마다 그 답을 한 줄에 하나씩 출력한다.

• $2 \le N \le 200$
• $1 \le M \le \frac{N(N-1)}{2}$
• $1 \le Q \le 10^6$
• $1 \le t_i \le 10^4$
• $1 \le u, v \le N$; $u \neq v$
• $1 \le w \le 10^7$
• $1 \le r \le N$
• $1 \le c \le 100$
• $1 \le a, b \le N$; $a \neq b$
• 모든 입력은 정수이다.