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