Нападения

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

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

Вам известно, что всего было зафиксировано $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.

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