Нападения

К сожалению, не все вампиры являются вегетарианцами, из-за чего периодически происходят неприятные события. Например, в последнее время в некоторых городах стали пропадать люди.

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

Вам известно, что всего было зафиксировано $m$ фактов пропаж людей. Про каждое такое событие вам известно время, в которое оно произошло (в часах от начала месяца), а также город, в котором оно произошло. Необходимо определить минимальное количество вампиров, которые могут стоять за этим.

Нападения, совершенные в моменты времени $t_1$ и $t_2$ могут быть совершены одним и тем же вампиром, если он может добраться из города, в котором произошло одно событие, до города, в котором произошло второе, менее чем за $|t_2 - t_1|$ часов.

Найдите минимальное количество вампиров, которые могут стоять за атаками на людей.

В первой строке задано целое число $T$ ($1 \le T \le 100$) --- количество тестов. Каждый из тестов описывается следующим образом.

В первой строке задано три целых числа $n$, $m$ и $k$ ($1 \le n, m \le 500$, $1 \le k \le 10^5$) --- количество городов, количество атак, а также количество дорог между городами. В следующих $m$ строках записано по два числа $t_i$ и $v_i$ ($1 \le t_i \le 10^6$, $1 \le v_i \le n$) --- время в часах, а также город, в котором произошла очередная атака. В следующих $k$ строках содержится по три числа $a_i$, $b_i$ и $c_i$ ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10^6$), которые описывают дорогу между городами $a_i$ и $b_i$. Вампиры могут воспользоваться этой дорогой и добраться из одного города в другой потратив $c_i$ часов.

Гарантируется, что суммарное количество городов во всех тестах не превышает 500. Аналогично, суммарное количество атак не превышает 500, а дорог --- 100,000.

Для каждого теста в отдельной строке выведите минимальное количество вампиров, которые могут стоять за нападениями на людей.