P10932 Freda's Pager

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.

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 $Q$ lines. Each line contains one integer, which is the result of each experiment.

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