#169 마법 토끼

Statement

$N$ 개의 정점과 $M$ 개의 양방향 간선으로 이루어진 연결 그래프가 있다. 정점은 $1,2,\ldots,N$ 번으로 번호가 붙어 있다.

각 정점 $i$ 에는 $A_i$ 개의 마나가 놓여 있다. 각 간선에는 양의 정수 용량 제한이 있다.

토끼는 여행을 할 수 있다. 여행은 다음 규칙을 따른다.

토끼는 임의의 정점에서 시작할 수 있다.
처음에 토끼가 가진 마나는 $0$ 개이다.
토끼가 현재 정점에 아직 주워지지 않은 마나가 남아 있다면, 그 마나 중 하나를 주울 수 있다. 마나 하나를 주우면 토끼가 가진 마나의 개수가 $1$ 증가한다.
토끼는 현재 정점과 인접한 정점으로 이동할 수 있다. 단, 현재 토끼가 가진 마나의 개수가 이동하려는 간선의 용량 이하일 때만 그 간선을 지날 수 있다.
한 번 주운 마나는 다시 내려놓을 수 없으며, 각 정점의 각 마나는 최대 한 번만 주울 수 있다.

$Q$ 개의 쿼리가 주어진다. 각 쿼리는 세 정수 $s_i,t_i,w_i$ 로 주어진다.

$i$ 번째 쿼리에서는 기존 그래프에 정점 $s_i$ 와 정점 $t_i$ 를 잇는 용량 $w_i$ 의 양방향 간선을 하나 추가한다고 가정한다. 이 간선은 해당 쿼리에서만 임시로 추가되며, 다음 쿼리에는 영향을 주지 않는다.

이때 추가된 간선을 포함한 그래프에서, 정점 $t_i$ 에서 끝나는 여행 중 토끼가 모을 수 있는 마나 개수의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ M\ Q$ $A_1\ A_2\ \cdots\ A_N$ $u_1\ v_1\ c_1$ $u_2\ v_2\ c_2$ $\vdots$ $u_M\ v_M\ c_M$ $s_1\ t_1\ w_1$ $s_2\ t_2\ w_2$ $\vdots$ $s_Q\ t_Q\ w_Q$

여기서 $u_j,v_j$ 는 $j$ 번째 기존 간선의 양 끝 정점이고, $c_j$ 는 그 간선의 용량이다.

$Q$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 쿼리의 정답을 출력한다.

일부 서브태스크에는 다음 특수조건이 적용된다.

특수조건 A: 모든 쿼리에 대해 $t_i=1$ 이다.
특수조건 B: $M=N-1$ 이고, 모든 $1 \le j < N$ 에 대해 $u_j=j$ , $v_j=j+1$ 이다. 또한 기존 간선의 용량은 $1$ 이상 $1\,000\,000\,000$ 이하의 범위에서 무작위로 생성된다.

입력

출력

6
4
6

첫 번째 쿼리에서는 용량 $2$ 의 간선 $(1,3)$ 이 임시로 추가된다. 정점 $1$ 의 마나를 먼저 $2$ 개 줍고, 임시 간선으로 정점 $3$ 으로 이동한 뒤, 정점 $2$ 와 정점 $3$ 의 마나까지 모두 주울 수 있다.

두 번째 쿼리의 목표 정점은 $2$ 이며, 최대 $4$ 개의 마나를 모을 수 있다.

세 번째 쿼리에서는 용량 $10$ 의 간선 $(2,1)$ 이 임시로 추가되어 모든 마나를 모을 수 있다.