时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给出 \(n\) 个城市间的 \(m\) 条航线以及对应的机票价格，要求回答一些询问，每个询问是给出最大停留次数 \(k\)，求从起点城市 \(s\) 到终点城市 \(t\)，经过的总城市数量(包括 \(s\) 和 \(t\))不超过 \(k\) 的最便宜的行程。

【输入格式】

　　第一行为 \(n，m，s\)，接下来的 \(m\) 行，每行表示一条航线：\(a,b,c\)，表示该航线在 \(a,b\) 两个城市间，机票价格为 \(c\)。接下来一个整数 \(q\)，表示询问次数。下面的 \(q\) 行，每行一个询问：\(t　k\)，表示从 \(s\) 到 \(t\)，中间停留次数不超过 \(k\) 次的最便宜行程。

【输出格式】

　　对每个询问，输出一行，表示最便宜行程。如果无法到达，则输出inf。

【输入输出样例】

　Input

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

　Output

4
3
8
7

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤10000\)，\(1≤m≤50000\)，\(1≤c≤30000\)，\(1≤k≤10\)，\(1≤q≤10000\)。

【来源】

　　Mr.he