{"raw_statement":[{"iden":"problem statement","content":"There are $N$ towns numbered $1,\\ldots,N$ and $M$ roads numbered $1,\\ldots,M$.\nRoad $i$ connects towns $A_i$ and $B_i$. When you use a road, your **score** changes as follows:\n\n*   when you move from town $A_i$ to town $B_i$ using road $i$, your score increases by $C_i$; when you move from town $B_i$ to town $A_i$ using road $i$, your score decreases by $C_i$.\n\nYour score may become negative.\nAnswer the following $Q$ questions.\n\n*   If you start traveling from town $X_i$ with initial score $0$, find the maximum possible score when you are at town $Y_i$.  \n    Here, if you cannot get from town $X_i$ to town $Y_i$, print `nan` instead; if you can have as large a score as you want when you are at town $Y_i$, print `inf` instead."},{"iden":"constraints","content":"*   $2\\leq N \\leq 10^5$\n*   $0\\leq M \\leq 10^5$\n*   $1\\leq Q \\leq 10^5$\n*   $1\\leq A_i,B_i,X_i,Y_i \\leq N$\n*   $0\\leq C_i \\leq 10^9$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$A_1$ $B_1$ $C_1$\n$\\vdots$\n$A_M$ $B_M$ $C_M$\n$X_1$ $Y_1$\n$\\vdots$\n$X_Q$ $Y_Q$"},{"iden":"sample input 1","content":"5 5 3\n1 2 1\n1 2 2\n3 4 1\n4 5 1\n3 5 2\n5 3\n1 2\n3 1"},{"iden":"sample output 1","content":"\\-2\ninf\nnan\n\nFor the first question, if you use road $5$ to move from town $5$ to town $3$, you can have a score $-2$ when you are at town $3$.  \nSince you cannot make the score larger, the answer is $-2$.\nFor the second question, you can have as large a score as you want when you are at town $2$ if you travel as follows: repeatedly \"use road $2$ to move from town $1$ to town $2$ and then use road $1$ to move from town $2$ to town $1$\" as many times as you want, and finally use road $2$ to move from town $1$ to town $2$.\nFor the third question, you cannot get from town $3$ to town $1$."},{"iden":"sample input 2","content":"2 1 1\n1 1 1\n1 1"},{"iden":"sample output 2","content":"inf\n\nThe endpoints of a road may be the same, and so may the endpoints given in a question."},{"iden":"sample input 3","content":"9 7 5\n3 1 4\n1 5 9\n2 6 5\n3 5 8\n9 7 9\n3 2 3\n8 4 6\n2 6\n4 3\n3 8\n3 2\n7 9"},{"iden":"sample output 3","content":"inf\nnan\nnan\ninf\n-9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}