问题1192--dzerzhinski 的王国

1192: dzerzhinski 的王国

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MB

题目描述

dzerzhinski 终于有一天成立了自己的acm王国,但与此同时他被一件事愁坏了(没有什么事情能难倒dzerzhinski,他只是假装愁坏了,因为这样才能考你),于是他来求助你。 

在dzerzhinski的王国里面有N个区域,不同区域间通过M条道路连接,道路是双向的,每条道路有着相应的长度Si。王国有一个首都,首都的编号为1,存在着K条特殊的道路能够直接从首都前往到另一个区域,这类道路各自也有对应的长度yi,我们把这类道路称为快速转移道路。保证首都能够通过道路直接或者间接到达任意区域。  

dzerzhinski想拆掉一些快速转移道路,他想知道最多可以同时移除多少条快速转移导读使得从中心区域到任意区域的最短长度不变。 



输入

第一行有三个整数N, M, K (2≤N105, 1M105, 1≤K≤105),分别代表区域数,道路数和快速转移道路数。
接下来 M 行每行三个整数u,v,S(1u,v≤N, u≠v, 1<S≤109)表示存在一条从 u 到 v 的长度为 S 的道路。
接下来 K 行每行两个整数u,y(1u≤N, 0<y≤109)表示存在一条从首都到 u 的长度为 y 的快速转移道路。
注意两个区域间可能有多条道路直接相连,因此,首都也可能与同一区域有着多条快速转移道路。

输出

输出一个数,代表最多可以同时去除的快速转移。

样例输入 Copy

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

样例输出 Copy

2

来源/分类