3512. Freda的传呼机

【题目描述】

为了随时与 Rainbow 快速交流，Freda 制造了两部传呼机。Freda 和 Rainbow 所在的地方有$n$座房屋、$m$条双向光缆。每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费$t$单位时间。

现在 Freda 要进行$q$次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。

$n$座房屋通过光缆一定是连通的，并且这$m$条光缆有以下三类连接情况：

  A：光缆不形成环，也就是光缆仅有$n-1$条。

  B：光缆只形成一个环，也就是光缆仅有$n$条。

  C：每条光缆仅在一个环中。

请你帮帮他们。

【输入格式】

第一行包含三个用空格隔开的整数，$n,m$和$q$。

接下来$m$行每行三个整数$x,y,t$，表示房屋$x$和$y$之间有一条传递时间为$t$的光缆。

最后$q$行每行两个整数$x,y$，表示 Freda 想知道在$x$和$y$之间传呼最少需要多长时间。

【输出格式】

输出$q$行，每行一个整数，表示 Freda 每次试验的结果。

【样例输入1】

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

【样例输出1】

3
1

【样例输入2】

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

【样例输出2】

3
1

【样例输入3】

9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7

【样例输出3】

5
6

【数据规模与约定】

其中10%的数据，$2\leq n\leq 1000,n-1\leq m\leq 1200$。

A类数据占30%，$m=n-1$。

B类数据占50%，$m=n$。

C类数据占10%，$m>n$。

对于100%的数据，$2\leq n\leq 10000,n-1\leq m\leq 12000, q=10000,1\leq x,y\leq n,1\leq t< 32768$。

【来源】

石家庄二中【Nescafé 26】杯NOIP模拟赛