题目描述

Jzzhu 是 A 国的总统。A 国有 $n$ 座城市，编号为 $1$ 到 $n$，其中 $1$ 号城市是首都。

国内有 $m$ 条公路。第 $i$ 条公路连接城市 $u_i$ 和 $v_i$，可以双向通行，长度为 $x_i$。

此外，国内还有 $k$ 条铁路。第 $i$ 条铁路连接首都和城市 $s_i$，可以双向通行，长度为 $y_i$。

Jzzhu 不想浪费国家的钱，所以准备关闭一些铁路。但他要求：关闭铁路后，每座城市到首都的最短距离都不能改变。

请你求出最多可以关闭多少条铁路。

输入格式

第一行包含三个整数 $n,m,k$（$2\le n\le 10^5$，$1\le m\le 3\cdot 10^5$，$1\le k\le 10^5$）。

接下来 $m$ 行，每行三个整数 $u_i,v_i,x_i$（$1\le u_i,v_i\le n$，$u_i\ne v_i$，$1\le x_i\le 10^9$），表示一条公路。

接下来 $k$ 行，每行两个整数 $s_i,y_i$（$2\le s_i\le n$，$1\le y_i\le 10^9$），表示一条连接首都和城市 $s_i$ 的铁路。

保证每座城市都能到达首都。允许两座城市之间有多条公路，也允许首都在同一座城市有多条铁路。

输出格式

输出一个整数，表示最多可以关闭的铁路数量。

样例

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

2

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

2

2 1 1
1 2 10
2 5

0

样例解释

样例 1 中，可以关闭到城市 $3$ 和城市 $5$ 的铁路，城市 $4$ 的铁路需要保留，因此最多关闭 $2$ 条。

样例 2 中，三条铁路到城市 $2$ 的长度分别为 $1,2,3$，保留最短的一条即可，另外两条可以关闭。

样例 3 中，城市 $2$ 到首都不是只有公路的最短路，铁路长度 $5$ 是最短路径，必须保留，因此一条也不能关闭。

数据范围与约定

对于 $100\%$ 的数据，$2\le n\le 10^5$，$1\le m\le 3\cdot 10^5$，$1\le k\le 10^5$，$1\le x_i,y_i\le 10^9$，保证每座城市都能到达首都。