Элитные Мартышки

Мартышки планируют встретиться в каком-то зоопарке. Помогите им найти зоопарк, который удовлетворяет их требованиям. Формально, вам нужно найти зоопарк $A$, такой, что для каждой мартышки $i$ выполняется следующее:

$\text{dist}(a_i, A) + \text{dist}(A, b_i) \leq d_i$

Или сообщить, что такого зоопарка не существует.

Формат Ввода

• Первая строка содержит одно целое число $T$, количество тестов.
• Затем, для каждого теста:
  • Первая строка содержит два целых числа, разделенных пробелом, $N, M$.
  • Затем следуют $N-1$ строк, каждая содержит два целых числа, разделенных пробелом, $x_i, y_i \ (1 \leq x_i, y_i \leq N, x_i \neq y_i)$, ребро дерева.
  • Затем следуют $M$ строк, описание требований мартышек, каждая содержит три целых числа, разделенных пробелом, $a_i, b_i, d_i \ (1 \leq a_i, b_i \leq N, 0 \leq d_i \leq 1 \ 000 \ 000 \ 000)$.

Ограничения

• $1 \leq T \leq 1 \ 000$
• $1 \leq N \leq 200 \ 000$
• $1 \leq M \leq 200 \ 000$
• Общая сумма $N$ во всех тестах не превышает $200 \ 000$.
• Общая сумма $M$ во всех тестах не превышает $200 \ 000$.

Формат Вывода

Для каждого теста выведите ответ (вы можете вывести любой, если существует несколько правильных зоопарков), или $-1$, если ответ не существует.

Система оценки

Пусть $S_N, S_M$ - общая сумма $N$ и $M$ соответственно во всех тестах.