{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou are given a directed weighted graph with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e nodes and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e edges. Your task is to find the minimum shortest path between any pair of nodes in the graph. As the weight of the edges can be negative, the path is allowed to visit the same node multiple times.\u003c/p\u003e\u003cp\u003eFormally, let \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e be the shortest path between the two nodes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e, find the minimum \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e over all pairs \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e)\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eu\u003c/i\u003e ≠ \u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e. If there is no path between a pair of nodes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e, then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e) \u003d ∞\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ 100)\u003c/span\u003e, the number of test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(2 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 2000)\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 5000)\u003c/span\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e is the number of nodes in the graph, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e is the number of edges.\u003c/p\u003e\u003cp\u003eEach of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e lines contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eU\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eV\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eC\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003eU\u003c/i\u003e, \u003ci\u003eV\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e)\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(\u003ci\u003eU\u003c/i\u003e ≠ \u003ci\u003eV\u003c/i\u003e)\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e( - 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e ≤ \u003ci\u003eC\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e)\u003c/span\u003e, representing that there is an edge from node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eU\u003c/i\u003e\u003c/span\u003e to node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eV\u003c/i\u003e\u003c/span\u003e with cost \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eC\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eNote that the graph may contain multiple edges between the same pair of nodes in the same direction.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print the minimum length of a shortest path in the graph, or \"-inf\" if the length of the shortest path is negative infinity.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 3\n1 2 -1\n2 3 -3\n3 1 -5\n4 5\n1 3 0\n1 2 -2\n2 3 3\n3 4 1\n4 1 -1\n4 4\n1 2 5\n2 3 -3\n3 4 -3\n1 4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-inf\n-3\n-6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}