#169 Rabbit

문제

$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$

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

#	Score	Constraints
1	5	$N,M,Q \le 10$ .
2	7	$N,M,Q \le 100$ .

Input

Output

6
4
6

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