题目描述

给出一个有 $N$ 个点 $M$ 条带权边的无向图，有 $B$ 次询问，每次询问给出两个整数 $x \ y$，求从点 $x$ 跑到点 $1$ 再跑到点 $y$ 的最短距离。

输入格式

第一行三个整数 $N,M,B(2\times B\le N\le 50000,N-1\le M\le 100000)$。

下来 $M$ 行，每行 $3$ 个整数 $x,y,L(1\le L \le 2000)$，表示一条从点 $x$ 到点 $y$ 权值为 $L$ 的有向边。

下来 $B$ 行，每行 $2$ 个整数 $x \ y$，表示一次询问。

输出格式

每次询问输出一个整数，即答案。

输入输出样例 #1

输入 #1

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

输出 #1

6 
6 
10