配点 : $500$ 点

問題文

$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 を代わりに出力せよ。

制約

• $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$
• 入力は全て整数である

入力

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

$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$ 番目の質問に対する答えを出力せよ。

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

$1$ 番目の質問では、道路 $5$ を使って街 $5$ から街 $3$ に移動すると、ポイントを $-2$ 所持している状態で街 $3$ にいることができます。 これ以上ポイントを大きくすることはできないので答えは $-2$ になります。

$2$ 番目の質問では、「道路 $2$ を使って街 $1$ から街 $2$ に移動し、道路 $1$ を使って街 $2$ から街 $1$ に移動する」 という行動を好きなだけ繰り返したあと、道路 $2$ を使って街 $1$ から街 $2$ に移動することで、 街 $2$ にいる状態で所持しているポイントをいくらでも増やすことができます。

$3$ 番目の質問では、街 $3$ から移動を始めて街 $1$ へ到達することはできません。

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