Problem Description

To communicate quickly with rainbow at any time, Freda made two pagers.

There are $N$ houses and $M$ undirected fiber-optic cables between the places where Freda and rainbow are located.

Each cable connects two houses. The pager signal can only travel along the cables, and it takes $t$ units of time for the signal to travel from one end of a cable to the other.

Now Freda will run $Q$ experiments. In each experiment, she picks two houses and wants to know the minimum time needed for the pager signal to travel between these two houses.

The $N$ houses are guaranteed to be connected by the cables, and these $M$ cables satisfy one of the following three types of connection:

• $A$: The cables do not form any cycle, i.e. there are only $N-1$ cables.
• $B$: The cables form exactly one cycle, i.e. there are only $N$ cables.
• $C$: Each cable belongs to exactly one cycle.

Please help them.

Input Format

The first line contains three integers separated by spaces: $N$, $M$, and $Q$.

The next $M$ lines each contain three integers $x,y,t$, meaning there is a cable between house $x$ and house $y$ with transmission time $t$.

The last $Q$ lines each contain two integers $x,y$, meaning Freda wants to know the minimum time needed to page between $x$ and $y$.

Output Format

Output $Q$ lines. Each line contains one integer, which is the result of each experiment.

5 4 2
1 2 1
1 3 1
2 4 1
2 5 1
3 5
2 1

3
1

Hint

Constraints: $2 \le N \le 10000$, $N-1 \le M \le 12000$, $Q = 10000$, $1 \le x,y \le N$, $1 \le t < 32768$.

Translated by ChatGPT 5