Fine Dining#10399
The cows are heading back to the barn at the end of a long day, feeling both tired and hungry.
The farm consists of pastures, conveniently numbered from to . All the cows want to get to the barn, which is located in pasture . Each of the other n - 1 pastures contains one cow. The cows can move between pastures along undirected trails. The -th trail connects pastures a_i and b_i and takes time t_i to traverse. Every cow can reach the barn via some sequence of trails.
Being hungry, the cows would like to stop for a snack on their way home. Conveniently, of the pastures contain tasty haybales, and the -th haybale has a yumminess value y_i. Each cow is willing to stop at one haybale on her way to the barn, but only if this increases her travel time, compared with her shortest route to the barn, by at most the yumminess of the haybale she visits. Note that a cow "officially" visits at most one haybale to dine; it is fine if her route passes through other pastures with haybales — she simply ignores them.
For each cow, determine whether she can stop at some haybale on her way to the barn.
The first line contains three integers , , and k~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5, 1 \le k \le n). Each of the next lines contains three integers a_i, b_i, and t_i~(a_i \ne b_i, 1 \le t_i \le 10^4), describing a trail between pastures a_i and b_i that takes time t_i to traverse.
Each of the next lines describes one haybale and contains two integers: the number of the pasture where it is located and its yumminess value y_i~(1 \le y_i \le 10^9). Several haybales may be located in the same pasture.
Print n - 1 lines. The -th line should contain if the cow in pasture can stop to dine at some haybale on her way to the barn, and otherwise.
Example 1
In this example, the cow in pasture should stop for a meal, since her travel time increases by only (from to ), which does not exceed the yumminess of the haybale. The cow in pasture should obviously eat the hay in pasture , since this does not change her optimal route at all. The cow in pasture is an interesting case: at first glance, it may seem that her optimal route (of length ) would increase too much for the stop to be worthwhile. However, she does have a route that makes stopping for the hay worthwhile: go to pasture , then to pasture (where she eats the hay), and then back to pasture .