Description

yyjj是网瘾少女，今天的她也在打游戏。地图是一张有 $n$ 个点 $m$ 条边的联通的无向图（无重边无自环），各节点由 $1$ 到 $n$ 编号，她通过第 $i$ 条边要花费 $w_i$ 秒。yyjj 固定出现在 $1$ 号点，身为战士的她要以最少的时间到达敌方法师处解救 npc。

敌人会对 yyjj 施展等级为 $k$ 的重力法术，这会使 yyjj 每到达一个点都需要先休息 $k$ 秒（包括出发点和终点）。而 yyjj 的吟游诗人队友给 yyjj 加了个增益，使得 yyjj 能减少她经过的花费时间最多的一条边的时间。

yyjj 和她的队友打算刷这个副本 $q$ 次，给出每次敌人出现的位置 $x$ 和敌方法师的法术等级 $k$，求出 yyjj 能到达敌人所在点的最少的时间。

Format

Input

第一行三个整数 $n,m,q$ $(2\le n \le 400; n-1\le m\le\frac{n(n-1)}{2}; 1\le q \le 10^5)$，分别表示图中点的数量，边的数量和刷副本次数。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$ $(1\le u_i,v_i\le n; 1\le w_i \le 5000)$，表示 $u_i$ 和 $v_i$ 之间有一条边相连，通过这条边要花 $w_i$ 的时间。保证整张图联通，没有重边和自环。

接下来 $q$ 行，每行两个整数 $x,k$ $(1 \le x\le n; 1\le k \le 10^5)$，表示这次副本中敌人所在的点的位置和敌人法术等级。

Output

应输出 $q$ 行，每行一个整数，表示该次副本中 yyjj 最少要花多少时间到达敌人所在的点。

Samples

7 7 2
1 2 50
2 3 10
1 4 1
4 5 1
5 6 1
6 7 1
7 3 1
3 1
3 5

10
25

Note

第一个样例中：

第一次敌方施加的的重力法术等级为 $1$，yyjj 的行进路线为：$1 \to 4 \to 5 \to 6 \to 7 \to 3$。yyjj 经过 $5$ 个节点，总共额外休息了 $5$ 秒，减去最耗时的一条边后，总花费时间为 $5+5=10$ 秒。

第二次敌方施加的的重力法术等级为 $5$，yyjj 的行进路线为：$1 \to 2 \to 3$。yyjj 经过 $3$ 个节点，总共额外休息了 $15$ 秒，减去最耗时的一条边后，总花费时间为 $15+10=25$ 秒。

Limitation

1s, 1024KiB for each test case.