1 && 3 Graph

Sehun and Chanwoo have solved many graph problems and developed their own ideas about what makes a good one.

• Sehun thinks the input graph should be ordinary enough that it needs no special-case handling. In this problem, an ordinary graph is an undirected simple connected graph: there are no duplicate edges, every vertex is connected, and every edge joins two distinct vertices.
• Chanwoo thinks a graph becomes messy when it has too many high-degree vertices. More precisely, the number of vertices whose degree is at least $3$ must be less than $3$.

A graph satisfying both conditions is called a 1 && 3 graph. You are given a 1 && 3 graph with $V$ vertices and $E$ edges. Write a program that processes $Q$ queries asking for the shortest distance between two vertices.

The first line contains three integers $V$, $E$, and $Q$: the number of vertices, the number of edges, and the number of queries. $(2 \le V \le 500000; V-1 \le E \le 500000; 1 \le Q \le 200000)$

Each of the next $E$ lines contains three integers $x$, $y$, and $c$, meaning that there is an edge of weight $c$ between vertices $x$ and $y$. $(1 \le x,y \le V; 1 \le c \le 10^9; x \ne y)$

Each of the next $Q$ lines contains two integers $a$ and $b$. This query asks for the shortest distance between vertices $a$ and $b$. $(1 \le a,b \le V)$

All input values are integers, and the given graph is a 1 && 3 graph.

Print $Q$ lines. For each query, print its answer on its own line, in the same order as the input.