题目描述

$1,\ldots,N$ の番号がついた $N$ 個の街と、$1,\ldots,M$ の番号がついた $M$ 本の道路があります。

道路 $i$ は街 $A_i$ と $B_i$ を結んでいます。道路を通行すると、所持している ポイント が次の通り増減します。

• 道路 $i$ を使って、街 $A_i$ から街 $B_i$ に移動するときにはポイントが $C_i$ 増加し、街 $B_i$ から街 $A_i$ に移動するときにはポイントが $C_i$ 減少する。

所持しているポイントは負にもなりえます。

次の $Q$ 個の質問に答えてください。

• 所持しているポイントが $0$ である状態で街 $X_i$ から移動を始めたとき、街 $Y_i$ にいる状態で所持しているポイントの最大値を出力せよ。
  ただし、街 $X_i$ から街 $Y_i$ に到達できないときは nan、街 $Y_i$ にいる状態で所持しているポイントをいくらでも増やせるときは inf を代わりに出力せよ。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $\vdots$ $A_M$ $B_M$ $C_M$ $X_1$ $Y_1$ $\vdots$ $X_Q$ $Y_Q$

输出格式

問題文の指示通りに $Q$ 行出力せよ。
$i$ 行目には $i$ 番目の質問に対する答えを出力せよ。

题目大意

有 $n$ 个小镇，编号 $1$ ~ $n$，还有 $m$ 条路，编号 $1$ ~ $m$ 。

第 $i$ 条路连接 ${A_i}$ 和 ${B_i}$，当你走过一条路时，你的得分会遵循以下变化：

• 当你用第 $i$ 条路从 ${A_i}$ 到 ${B_i}$，你的得分增加 ${C_i}$ ; 当你用第 $i$ 条路从 ${B_i}$ 到 ${A_i}$，你的得分减少 ${C_i}$ 。

你的得分可能为负数。

回答如下的 $Q$ 个问题：

• 如果你从 ${X_i}$ 这个小镇出发（初始得分为 $0$ ）, 求出你在 ${Y_i}$ 小镇时的最大得分。

• 如果你不能从 ${X_i}$ 这个小镇出发到达 ${Y_i}$ 小镇，输出 nan 。

• 如果你从 ${X_i}$ 这个小镇出发到达 ${Y_i}$ 小镇可以挣得无限的分数，输出 inf 。

输出格式：

输出遵循以下格式：

$N$ $M$ $Q$

${A_1}$ ${B_1}$ ${C_1}$

……

${A_M}$ ${B_M}$ ${C_M}$

${X_1}$ ${Y_1}$

……

${X_M}$ ${B_M}$

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

-2
inf
nan

2 1 1
1 1 1
1 1

inf

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

inf
nan
nan
inf
-9

提示

制約

• $2\leq\ N\ \leq\ 10^5$
• $0\leq\ M\ \leq\ 10^5$
• $1\leq\ Q\ \leq\ 10^5$
• $1\leq\ A_i,B_i,X_i,Y_i\ \leq\ N$
• $0\leq\ C_i\ \leq\ 10^9$
• 入力は全て整数である

Sample Explanation 1

$1$ 番目の質問では、道路 $5$ を使って街 $5$ から街 $3$ に移動すると、ポイントを $-2$ 所持している状態で街 $3$ にいることができます。 これ以上ポイントを大きくすることはできないので答えは $-2$ になります。 $2$ 番目の質問では、「道路 $2$ を使って街 $1$ から街 $2$ に移動し、道路 $1$ を使って街 $2$ から街 $1$ に移動する」 という行動を好きなだけ繰り返したあと、道路 $2$ を使って街 $1$ から街 $2$ に移動することで、 街 $2$ にいる状態で所持しているポイントをいくらでも増やすことができます。 $3$ 番目の質問では、街 $3$ から移動を始めて街 $1$ へ到達することはできません。

Sample Explanation 2

始点と終点が同じ街である道路や、始点と終点が同じ街である質問が含まれることもあります。