题目描述

$n$ 个点，$m$ 条带权边的无向图，另外还有 $k$ 条特殊边，每条边连接 $1$ 和 $s_i$。

问最多可以删除这 $k$ 条边中的多少条，使得每个点到 $1$ 的最短距离不变。

输入格式

第一行 $3$ 个数字 $n,m,k$，$1\le n,k\le 10^5$，$1\le m\le 3\times 10^5$。

下面 $m$ 行，每行 $3$ 个数字 $u_i,v_i,x_i\ (u_i\ne v_i)$，表示顶点 $u_i,v_i$ 之间有一条边，权值为 $x_i$，$1\le x_i\le 10^9$。

再下面 $k$ 行，每行两个数字 $s_i,y_i$，代表连接 $1$ 与 $s_i$ 的边，权值为 $y_i$，$1\le y_i\le 10^9$。

输出格式

输出一个整数表示答案。

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