{"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\u003eBạn được cho một đồ thị có hướng có trọng số với \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e đỉnh và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e cạnh. Nhiệm vụ của bạn là tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị. Vì trọng số của các cạnh có thể là số âm, nên đường đi được phép ghé qua cùng một đỉnh nhiều lần.\u003c/p\u003e\u003cp\u003eCụ thể, cho \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e là đường đi ngắn nhất giữa hai đỉnh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e, tìm giá trị nhỏ nhất của \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eF\u003c/i\u003e(\u003ci\u003eu\u003c/i\u003e, \u003ci\u003ev\u003c/i\u003e)\u003c/span\u003e trên tất cả các cặp \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. Nếu không có đường đi giữa một cặp đỉnh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e, thì \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":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên của input chứa một số nguyên \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, số lượng test cases.\u003c/p\u003e\u003cp\u003eDòng đầu tiên của mỗi test case chứa hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e và \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, trong đó \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e là số lượng đỉnh trong đồ thị, và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e là số lượng cạnh.\u003c/p\u003e\u003cp\u003eMỗi trong số \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e dòng tiếp theo chứa ba số nguyên \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 và \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, biểu diễn rằng có một cạnh từ đỉnh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eU\u003c/i\u003e\u003c/span\u003e đến đỉnh \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eV\u003c/i\u003e\u003c/span\u003e với chi phí \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eC\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eLưu ý rằng đồ thị có thể chứa nhiều cạnh giữa cùng một cặp đỉnh trong cùng một hướng.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eĐối với mỗi test case, in ra độ dài nhỏ nhất của một đường đi ngắn nhất trong đồ thị, hoặc \"-inf\" nếu độ dài của đường đi ngắn nhất là âm vô cùng.\u003c/p\u003e"}},{"title":"Ví dụ 1","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"}}]}