드래곤 죽이기

드래곤 나라에는 도시 $N$개와 도로 $M$개가 있다. 도시에는 $1$번부터 $N$번까지 번호가 붙어 있고, 도로는 서로 다른 두 도시를 잇는다. 도로는 양방향으로 지나갈 수 있다.

이 나라에는 드래곤 $K$마리가 산다. $i$번째 드래곤은 도시 $C_i$에 살고, 처음에 머리가 $S_i$개 있으며, 살아 있는 동안 매 분 머리가 $N_i$개씩 새로 자란다. 머리가 하나라도 남아 있는 드래곤은 살아 있고, 머리가 모두 잘린 드래곤은 죽는다. 죽은 드래곤은 머리가 다시 자라지 않는다.

드래곤을 모두 없애려고 워리어를 고용한다. 워리어마다 시작 도시를 우리가 정하고, 1분부터 매 분이 다음 순서로 진행된다.

1. 워리어마다 셋 중 하나를 한다. 도로로 이어진 도시 하나로 이동한다. 지금 있는 도시의 살아 있는 드래곤 하나를 골라 머리를 하나 자른다. 아무것도 하지 않는다.
2. 그 분의 행동이 모두 끝난 뒤, 머리가 하나라도 남은 드래곤마다 머리가 $N_i$개 자란다.

한 도시에 드래곤이 여러 마리 살 수도 있고, 여러 워리어가 같은 분에 같은 드래곤의 머리를 잘라도 된다. 워리어는 도로로만 다니므로 도로로 이어지지 않은 도시 사이는 오갈 수 없다.

워리어의 시작 도시와 매 분의 행동을 모두 우리가 정한다. 유한한 시간 안에 드래곤을 모두 죽이는 데 필요한 워리어의 최소 수를 구하라.

입력은 테스트 케이스 여러 개로 이루어진다.

각 테스트 케이스의 첫 줄에 정수 $N$, $M$, $K$ ($1 \le N \le 300$, $0 \le M \le N(N-1)$, $1 \le K \le 1000$)가 주어진다. 다음 $M$개 줄에는 도로가 한 줄에 하나씩 주어지며, 각 줄에는 도시 $a$와 도시 $b$를 잇는 도로를 뜻하는 정수 $a$, $b$ ($1 \le a \ne b \le N$)가 주어진다. 같은 두 도시를 잇는 도로가 여러 번 주어질 수도 있다. 다음 $K$개 줄에는 드래곤이 한 줄에 한 마리씩 주어지며, $i$번째 줄에는 정수 $C_i$, $S_i$, $N_i$ ($1 \le C_i \le N$, $1 \le S_i \le 10^5$, $0 \le N_i \le 10^5$)가 주어진다.

마지막 테스트 케이스 다음 줄에는 0 0 0이 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 드래곤을 모두 죽이는 데 필요한 워리어의 최소 수를 한 줄에 출력한다.