该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

指定地点会合

城市中有 $n$ 个地点和 $m$ 条单向道路．第 $i$ 条道路从 $u_i$ 通向 $v_i$，经过它需花费 $w_i$．两个人可以经过同一条道路，互不影响．

有一个人总从地点 $1$ 出发，另一个人从地点 $p$ 出发．他们各自沿单向道路行走，最终在同一个允许会合的地点 $v$ 会合．选择地点 $v$ 还需支付一次服务费 $c_v$；两人的行走费用加上这笔服务费，就是此次会合的总费用．

给定允许会合的地点及其服务费．对每个 $p=1,2,\ldots,n$，求可能的最小总费用；若无法会合，输出 $-1$．允许两人一开始就在会合点，且道路可以被重复经过．每个 $p$ 对应一次独立的计算．

输入格式

第一行输入三个整数 $n,m,k$，分别表示地点数、道路数和允许会合的地点数．

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$，表示一条单向道路．

接下来 $k$ 行，每行两个整数 $v,c_v$，表示一个允许会合的地点及其服务费．会合点互不相同．

输出格式

输出一行 $n$ 个整数，第 $p$ 个数是第二个人从地点 $p$ 出发时的答案；若无法会合，该数为 $-1$．

样例 1

4 5 2
1 2 2
2 3 2
4 3 1
1 4 10
3 4 4
2 1
3 0

5 3 4 5

例如，第二个人从地点 $4$ 出发时，双方可在地点 $3$ 会合．第一人从 $1$ 经 $2$ 到 $3$ 花费 $4$，第二人从 $4$ 到 $3$ 花费 $1$，服务费为 $0$，总费用为 $5$．

更多样例

点击下载本题选手目录

• Data/sample1.in 与 Data/sample1.ans：题面样例．
• Data/sample2.in 与 Data/sample2.ans：$n=300,m=300$，含环、重边与不可达地点，符合子任务 1．
• Data/sample3.in 与 Data/sample3.ans：$n=100000,m=199998$，道路成对双向出现，全部地点可免费会合，符合子任务 2．
• Data/sample4.in 与 Data/sample4.ans：$n=100000,m=200000,k=1$，含环与不可达地点，符合子任务 3．
• Data/sample5.in 与 Data/sample5.ans：$n=100000,m=200000$，道路构成有向无环图，符合子任务 4．
• Data/sample6.in 与 Data/sample6.ans：$n=100000,m=200000$，含有向环、不同服务费与不可达地点，该样例无特殊限制．

下载样例与正式评测数据独立构造．通过这些样例不代表解法正确，也不保证获得相应子任务的分数．

数据范围与子任务

对于所有数据，$2\le n\le10^5$，$0\le m\le2\times10^5$，$1\le k\le n$；$1\le u_i,v_i\le n$ 且 $u_i\ne v_i$，$1\le w_i\le10^9$，$1\le v\le n$，$0\le c_v\le10^9$．不同道路可以有相同端点，不保证地点之间可以相互到达．答案可能超过 32 位有符号整数范围．

各子任务独立计分；只有通过该子任务的全部测试点，才能获得其分数．