Hungry Cows' Haybale Detour

After a long day, the starving cows are ready to return to the barn. The farm consists of (N) pastures (numbered from (1) to (N)) with pasture (N) hosting the barn. In each of the other (N-1) pastures there is one cow. The pastures are connected by (M) undirected roads; the (i)th road connects pasture (a_i) with pasture (b_i) and takes (t_i) time to traverse. Every cow can reach the barn via some sequence of roads.

Due to hunger, each cow would like to stop along her way to the barn at a hay bale location to forage. There are (K) hay bales on the farm. The (i)th hay bale is located in a pasture and has a flavor value of (y_i). A cow will only decide to officially stop at a hay bale if the detour – that is, the extra time incurred compared to taking the fastest route to the barn – is at most the flavor value of that hay bale. Note that even if a cow passes by other hay bale locations along her route, she will only stop (officially) for one hay bale.

Formally, let (d(u)) be the shortest time from pasture (u) to the barn. For a cow starting at pasture (i) ((1 \le i \le N-1)), if there exists a hay bale located at pasture (p) with flavor (y) such that [ d(i, p) + d(p) - d(i) \le y,] then the cow can afford to stop there. Your task is to determine, for each cow (in pastures (1) through (N-1)), whether she can take a detour to eat a hay bale without exceeding the extra time allowed by its flavor.

inputFormat

The first line contains three integers (N), (M), and (K) ((2 \le N \le 5\times10^4,; 1 \le M \le 10^5,; 1 \le K \le N)).

The next (M) lines each contain three integers (a_i), (b_i), and (t_i), describing an undirected road between pastures (a_i) and (b_i) with travel time (t_i).

The next (K) lines each contain two integers. In each of these lines, the first integer is the pasture where a hay bale is located and the second integer is its flavor value (y). It is possible that multiple hay bales are in the same pasture.

outputFormat

Output exactly (N-1) lines. The (i)th line (for (1 \le i \le N-1)) should contain a single integer: output 1 if the cow in pasture (i) can take a detour to eat a hay bale without exceeding the extra time allowed, or 0 otherwise.

sample

3 3 1
1 2 5
2 3 5
1 3 12
1 3

1
0