该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

关于SPFA，它死了......

全知全能的神知道后于是赐予它在随机图，稀疏图以及负权图上的神力，并为它准备了一场复活仪式。

但是复活并不简单，单源最短路对于它并不算是什么考验。于是复活的考验变成了全源最短路，但是为了降低难度，神将考验的场地变成了极度稀疏的稀疏图，并为它开了超大时限。

仪式已经开始，复活吧!......

题目描述

给出包含$N$个点，$M$条边的无向连通图，保证$M-N \le 20$。

每次给出一对点$a_i,b_i$请输出它们之间的最短路的长度。

注意：本题与只是借用SPFA的背景，考虑到它的不稳定性，请谨慎使用。

输入格式

第一行有三个数$n,m,q(1 \le n ,m, q \le 10^5,m-n \le 20)$表示无向图的点数，边数与询问次数。

接下来$m$行每行包含三个数$u_i,v_i,w_i(1\le u_i,v_i\le n,u_i \ne v_i,1\le w_i \le 10^9)$表示点$u_i$与$v_i$之间有一条长度为$w_i$的无向边相连。

接下来q行每行包含两个数$a_i,b_i$表示询问点$a_i$与点$b_i$之间的最短路径长度。

保证不存在重边与自环。

输出格式

输出包含$m$行,第$i$行表示第$i$次询问的答案。

样例 #1

样例输入 #1

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

样例输出 #1

3
1
4

样例 #2

样例输入 #2

8 13 8
1 2 4
2 3 6
3 4 1
4 5 12
5 6 3
6 7 8
7 8 7
1 4 1
1 8 3
2 6 9
2 7 1
4 6 3
6 8 2
1 5
1 7
2 3
2 8
3 7
3 4
6 8
7 8

样例输出 #2

7
5
6
7
7
1
2
7