U327466 铁路

难度：提高 CW国有n个城市，城市之间有m条公路，和k条铁路，铁路都是连接首都和其他城市的，公路和铁路都是双向的，1号城市为首都。为了节约成本，总统决定在首都到其他城市的最短路不变的前提下关闭一些铁路，求最多关闭多少条铁路。

第一行三个正整数n,m,k 接下来m行为公路的描述：a,b,c表示连接城市a,b的公路长度为c 接下来k行为铁路的描述：x,y表示连接首都和城市x的铁路长度为y

一行一个数，表示最多关闭的铁路条数。

#### 数据范围 对于30%的数据， 2 ≤ n ≤ 100; 1 ≤ m ≤ 300; 1 ≤ k ≤ 100 对于60%的数据， 2 ≤ n ≤ 1000; 1 ≤ m ≤ 3000; 1 ≤ k ≤ 1000 对于100%的数据，2 ≤ n ≤ 1e5; 1 ≤ m ≤ 3e5; 1 ≤ k ≤ 1e5,1 ≤ c,y ≤ 1e9