You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

漫长的一天结束了，饥困交加的奶牛们准备返回牛棚。

农场由 N 片牧场组成（2≤N≤5×10^4），方便起见编号为 1…N。所有奶牛都要前往位于牧场 N 的牛棚。其他 N−1 片牧场中每片有一头奶牛。奶牛们可以通过 M 条无向的小路在牧场之间移动（1≤M≤10^5）。第i条小路连接牧场 ai和 bi，通过需要时间 ti。每头奶牛都可以经过一些小路回到牛棚。

由于饥饿，奶牛们很乐于在他们回家的路上停留一段时间觅食。农场里有 K 个有美味的干草捆，第 i个干草捆的美味值为 yi。每头奶牛都想要在她回牛棚的路上在某一个干草捆处停留，但是她这样做仅当经过这个干草捆使她回牛棚的时间增加不超过这个干草捆的美味值。注意一头奶牛仅仅“正式地”在一个干草捆处因进食而停留，即使她的路径上经过其他放有干草捆的牧场；她会简单地无视其他的干草捆。

输入格式

输入的第一行包含三个空格分隔的整数 N,M 和 K。以下 M 行每行包含三个整数 ai，bi​和 ti，表示牧场 ai和 bi之间有一条需要 ti时间通过的小路（ai不等于 bi，ti为不超过 10^4 的正整数）。

以下 K 行，每行以两个整数描述了一个干草捆：该干草捆所在牧场的编号，以及它的美味值（一个不超过 10^9 的正整数）。同一片牧场中可能会有多个干草捆。

输出格式

输出包含 N−1 行。如果牧场 i 里的奶牛可以在回牛棚的路上前往某一个干草捆并且在此进食，则第 i 行为一个整数 1，否则为一个整数 0。

输入输出样例

输入 #1复制

4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7

输出 #1复制

1
1
1

样例说明

在这个例子中，牧场 3 里的奶牛可以停留进食，因为她回去的时间仅会增加 6（从 2 增加到 8），而这个增加量并没有超过干草捆的美味值 7。牧场 2 里的奶牛显然可以吃掉牧场 2 里的干草，因为这并不会导致她的最佳路径发生变化。对于牧场 1 里的奶牛是一个有趣的情况，因为看起来她的最佳路径（10）可能会因为前去进食而有过大的增加量。然而，确实存在一条路径使得她可以前去干草捆处停留：先到牧场 4，然后去牧场 2（吃草），然后回到牧场 4。