题目内容

小塔有一个$n$个点 $m$ 条边的无向图，每条边有一个权值 $w_i$。

小塔现在计划修人条双向道路，起点是$1$号点，终点是其他顶点。

假设修了这$k$条路后，从$1$号点到其他点的距离为$d$，小塔想知道，可以少修多少条路，使得从 $1$ 号点到其他点的距离仍然为 $d$。

输入描述

第一行三个整数 $n,m,k$，表示点数，边数，以及小塔计划修的路数。

接下来 $m$ 行，每行三个整数$u_i,v_i,w_i$，表示一条边的两个端点以及权值。

接下来$k$行，每行两个整数$p_i，s_i$，表示计划修从$1$号点到$p_i$号点的一条路,长度为 $s_i$。

$1 ≤n,m,k≤10^5$

$1 ≤u_i,v_i,p_i≤10^5$

$1 ≤ w_i,s_i≤10^9$

输出描述

输出一个整数，表示可以少修的路数。

样例1

输入

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

输出

2

说明

从$1$号点到$2$号点的距离为$2$，修路不能改变最短距离，两条路都可以不修。