有 N 个好朋友，他们的编号为 1 \sim N，他们居住在同一个城市中，编号为 i 的好友居住在编号为 i 的小区中，今天是十一假期，他们决定一起驱车前往编号为 N 的好友家聚会。

车载导航地图中标注出了 N 个人居住小区的位置，以及小区之间 M 条双向道路。每个人（编号为 1 \sim N-1）将会以最短的路径，驱车前往编号为 N 的小区。

这 N 个小区中，共有 K 家连锁超市，一个小区中可能有多个超市。十一假期，所有的超市都会发放优惠券，不同的超市优惠券的额度有所不同。

对于编号为 i 的好友，他通过查询车载导航以及超市的优惠信息综合判断，如果满足如下条件，他就会到某个超市中购买一份美食带到 N 号小区和大家一起享用。

• 假设编号为 i 的好友不去任何超市，从自己居住的小区直接去编号为 N 的小区，路径长度为 D_{1i}。
• 如果编号为 i 的好友去了某家超市，该家超时发放的优惠券额度为 V_j ，由于需要去超市，该好友从家到某超市再到编号为 N 的小区，路径长度为 D_{2i}。
• 若满足 D_{2i} - D_{1i} \le V_j，则该好友觉得即使绕路去超市（注意：也可能是顺路，没有产生绕路）也是划算的，他就会选择去某超市购买美食，否则他不会购买任何美食。

请编程计算出，对于编号为 1 \sim N-1 的每个好友，他们是否会购买美食带到 N 号小区。

第一行输入三个整数 N, M, K，分别表示好友数量、道路数量、超市数量。

接下来 M 行，每行输入三个整数 U_i, V_i, L_i，表示编号为 U_i 和 V_i 的小区之间有一条长度为 L_i 的道路。

再接下来 K 行，每行输入两个整数，表示一个超市所在的小区编号及其发放优惠的金额 V_j，同一个小区可能存在多个超市。

输出 N-1 行，第 i 行输出一个整数：如果编号为 i 的好友会去超市购买美食，请输出数字 1，否则输出数字 0。

样例 1 说明

• 好友 1：最短路为 10。如果他选择先到小区 2 超市再去 4（即路径为：1 - 4 - 2 - 4），最短路为 18，总增加量超过 7，因此不会去超市。
• 好友 2：所在小区本身就有超市，绕路为 0，因此必然会去。
• 好友 3：直接到 4 的最短路为 2。若先到小区 2 的超市再去 4（即路径为：3 - 4 - 2 - 4），总路程为 10，比最短路径多 8。由于超市的优惠额度为 7，因此 他不会选择去超市。

【样例 4】

见选手目录下的 party/party4.in 与 party/party4.ans。

数据范围

对于 10\% 的数据，满足 N,M \le 10，K=1。

对于另外 20\% 的数据，满足 N \le 400，M \le 800，K \le 25。

对于 100\% 的数据，满足 2 \le N \le 5 \times 10^4，1 \le M \le 10^5，1 \le K \le N，1 \le U_i, V_i \le N，1 \le L_i \le 10^4，每个超市发放的优惠券的金额 1 \le V_j \le 10^9。

测试数据保证该图为连通图。

月赛图论分层图25年10月多源最短路