Элитные Роботы

Некоторые вершины оснащены зарядными устройствами для батарей. Робот, находящийся в данный момент на вершине с зарядным устройством, может мгновенно зарядить свою батарею до полной емкости (т.е. до $b_i$). Гарантируется, что как $U_i$, так и $V_i$ являются вершинами с зарядными устройствами для каждого робота $i$.

Робот перемещается по рёбрам одно за другим. Пересечение ребра $e$ потребляет $w_e$ единиц его текущей батареи. Робот может пересекать ребро только в том случае, если уровень его текущей батареи на данный момент составляет не менее $w_e$. Роботы могут посещать вершины и рёбра несколько раз и могут заряжаться любое количество раз на вершинах с зарядными устройствами. Роботы действуют независимо (без вмешательства или заторов).

Для каждого робота $i$ $(1 \le i \le Q)$ определите минимальную емкость батареи $b_i^\star$, такая что робот $i$ может начать на $U_i$ с полной батареей, следовать по какому-то маршруту, который соблюдает правила энергии и зарядки, и добраться до $V_i$.

Формат Ввода

• Первая строка содержит одно целое число $T \ (1 \leq T \leq 10^3)$ — количество тестов.
• Затем, для каждого теста:
  • Первая строка содержит три разделённых пробелами целых числа $N, M, Q \ (1 \leq N, M, Q \leq 2 \cdot 10^5)$.
  • Вторая строка содержит $N$ целых чисел $c_1, c_2, \ldots, c_N$.
    Если $$, то на вершине есть зарядное устройство для батарей. В противном случае .
  • Далее следуют $M$ строк, описывающих граф.
    Каждая строка состоит из трёх разделённых пробелами целых чисел $x_i, \ y_i, \ w_i$ ($$, ) — описание ребра . Между вершинами и существует ребро длиной . Граф может содержать несколько рёбер.
  • Затем следуют $Q$ строк, описывающих запросы.
    Каждая строка состоит из двух разделённых пробелами целых чисел $U_i, V_i$ ($1 \leq U_i, V_i \leq N$).

Гарантируется, что граф связен.

Ограничения:

• Общая сумма $N$ во всех тестах не превышает $2 \cdot 10^5$.
• Общая сумма $M$ во всех тестах не превышает $2 \cdot 10^5$.
• Общая сумма $Q$ во всех тестах не превышает $2 \cdot 10^5$.

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

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

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

Пусть $S_N$ — сумма $N$ во всех тестах.
С той же логикой пусть $S_M, S_Q$ — суммы $M$ и $Q$ соответственно.