Terrorists

The neighbourhood is described by intersections and roads. Terrorists gather at one intersection and then move to another intersection to commit a crime. The information the police collected records the meet up intersection and the destination intersection of each plan, but not the time.

The police are short of officers and cannot stop every crime on the spot. Instead they install a surveillance camera at every meet up intersection, and once a gathering is detected they head for that plan's destination. Terrorists always travel between intersections along a shortest route.

For each plan, compute the shortest distance between the meet up intersection and the destination intersection.

The first line contains the number of test sets $T$. ($1 \le T \le 5$)

The first line of each test set contains the number of intersections $N$, the number of roads $M$, and the number of terrorist plans $Q$, in that order. ($1 \le N \le 100000$, $N - 1 \le M \le N + 50$, $1 \le Q \le 50000$)

Each of the next $M$ lines describes one road with three integers $U$, $V$, $D$. $U$ and $V$ are the two intersections the road joins, and $D$ is its length. ($1 \le U, V \le N$, $1 \le D \le 10000$) Several roads may join the same pair of intersections, and a road may have $U$ equal to $V$. Every road is bidirectional, and every intersection is reachable from every other intersection.

Each of the next $Q$ lines describes one plan with two integers $S$ and $E$. $S$ is the meet up intersection and $E$ is the destination intersection. ($1 \le S, E \le N$)

For each test set, first print Case x:, where $x$ is the test set number starting from 1. Then print $Q$ lines, one per plan in the order given in the input, each holding the shortest distance between that plan's meet up intersection and its destination intersection.