← 返回题目列表

Codeforces · 449/B

B. Jzzhu 与城市

中文机器翻译题面 查看原题

Jzzhu是A国总统,他的国家有n个城市,编号从1到n。城市1是A的首都。连接城市的道路也有m条。人们可以使用第i条路从城市ui到vi(反之亦然),这条路的长度是xi。最后,全国有k条火车线路。可以使用第i条火车路线从该国首都到城市si(反之亦然),这条路线的长度为yi。

Jzzhu不想浪费国家的钱,所以他要关闭一些火车路线。请告诉Jzzhu,在以下条件下可以关闭的火车线路的最大数量:每个城市到首都的最短路径长度不得改变。

输入

第一行包含三个整数 n、m、k (2 ≤ n ≤ 105;1 ≤ m ≤ 3·105;1 ≤ k ≤ 105)。

接下来的 m 行中的每一行都包含三个整数 ui、vi、xi (1 ≤ ui, vi ≤ n;ui ≠ vi;1 ≤ xi ≤ 109)。

接下来的 k 行中的每一行都包含两个整数 si 和 yi (2 ≤ si ≤ n; 1 ≤ yi ≤ 109)。

保证每个城市到首都至少有一条路。请注意,两个城市之间可以有多条道路。此外,可以有多条路线从首都前往同一城市。

输出

输出一个整数,表示可以关闭的火车路线的最大数量。

示例

输入 #1

5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5

输出 #1

2

输入 #2

2 2 3
1 2 2
2 1 3
2 1
2 2
2 3

输出 #2

2