Killing Dragons

Dragon country has $N$ cities and $M$ roads. The cities are numbered $1$ through $N$, and each road joins two different cities. Every road can be walked in both directions.

$K$ dragons live in the country. Dragon $i$ lives in city $C_i$, starts with $S_i$ heads, and grows $N_i$ new heads every minute while it is alive. A dragon with at least one head is alive, and a dragon whose heads are all cut off dies. A dead dragon never grows a head again.

You hire warriors to wipe the dragons out. You pick the starting city of every warrior, and from minute 1 on, each minute runs in this order.

1. Every warrior does one of three things. Move to a city joined to the current city by a road. Pick one living dragon in the current city and cut off one of its heads. Do nothing.
2. Once all of that minute's actions are done, every dragon that still has at least one head grows $N_i$ more heads.

Several dragons may live in one city, and several warriors may cut heads off the same dragon in the same minute. Warriors travel only along roads, so they cannot move between cities that no chain of roads connects.

You choose the starting city and every action of every warrior. Find the smallest number of warriors that kills all of the dragons within a finite number of minutes.

The input holds several test cases.

The first line of each test case has three integers $N$, $M$, $K$ ($1 \le N \le 300$, $0 \le M \le N(N-1)$, $1 \le K \le 1000$). Each of the next $M$ lines holds one road as two integers $a$, $b$ ($1 \le a \ne b \le N$), a road between city $a$ and city $b$. The same pair of cities may be given more than once. Each of the next $K$ lines holds one dragon, and line $i$ has three integers $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$).

The line after the last test case is 0 0 0, and that line is not processed.

For each test case, print on one line the smallest number of warriors that kills all of the dragons.