题目描述

有一个包含 $N$ 个点、$M$ 条边的无向带权图，终点为 $N$。其中 $K$ 个点有超市，在点 $u$ 的超市购物可获得 $v$ 元优惠。

对每个起点 $i$（$1\le i<N$），如果从 $i$ 出发，经过某个超市购物后到达点 $N$ 的最小费用，不超过直接到达点 $N$ 的最短路费用，则输出 $1$；否则输出 $0$。

经过超市的费用等于行走路径长度减去该超市的优惠金额。

输入格式

第一行包含三个整数 $N,M,K$。

接下来 $M$ 行，每行包含三个整数 $u,v,w$，表示一条长度为 $w$ 的无向边。

接下来 $K$ 行，每行包含两个整数 $u,v$，表示点 $u$ 有一家优惠金额为 $v$ 的超市。

输出格式

输出 $N-1$ 行，第 $i$ 行表示起点 $i$ 的答案。

4 4 1
1 2 3
2 4 4
1 3 2
3 4 10
2 2

1
1
1

数据范围与提示

• $2 \le N \le 5\times10^4$
• $1 \le M \le 10^5$
• $1 \le K \le N$
• $1 \le u,v \le N$
• $1 \le w \le 10^9$
• 保证任意点都能到达点 $N$