Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

B. Jzzhu и города
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Jzzhu — президент страны A. В его стране есть n городов, пронумерованных от 1 до n. Город 1 — столица A. Также есть m дорог, соединяющих города. По i-й дороге можно дойти из города ui в город vi (и наоборот), длина этой дороги равна xi. Более того, в стране есть k железнодорожных маршрутов. По i-му маршруту можно доехать от столицы страны до города si (и наоборот), длина этого маршрута равна yi.

Jzzhu не хочет зря растрачивать государственный бюджет, поэтому он хочет закрыть некоторые железнодорожные маршруты. Пожалуйста, посчитайте для Jzzhu, какое максимальное количество железнодорожных маршрутов можно закрыть, если требуется выполнить следующее условие: длина кратчайшего пути из каждого города в столицу не должна измениться.

Входные данные

В первой строке записано три целых числа, n, m, k (2 ≤ n ≤ 105; 1 ≤ m ≤ 3·105; 1 ≤ k ≤ 105).

В каждой из следующих m строк записано три целых числа, ui, vi, xi (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ xi ≤ 109).

В каждой из следующих k строк записано два целых числа, si и yi (2 ≤ si ≤ n; 1 ≤ yi ≤ 109).

Гарантируется, что существует по крайней мере один путь из каждого города в столицу. Обратите внимание, что между двумя городами может быть несколько дорог. Также может быть несколько железнодорожных маршрутов, ведущих из одного и того же города в столицу.

Выходные данные

Выведите единственное целое число, обозначающее максимальное количество железнодорожных путей, которые можно закрыть.

Примеры
Входные данные
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