{"trustable":false,"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 bất kỳ trong mọi cặp đỉnh của đồ thị. Đường đi của bạn có thể đi qua một đỉnh hoặc một cạ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":"INPUT","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 là số lượng bộ dữ liệu.\u003c/p\u003e\u003cp\u003eDòng đầu tiên của mỗi bộ dữ liệu 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\n\u003cp\u003e\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eM\u003c/i\u003e\u003c/span\u003e dòng tiếp theo, mỗi dòng 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 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 trọng số \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eC\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eLưu ý rằng có thể có nhiều cạnh nối cùng một cặp đỉnh.\u003c/p\u003e"}},{"title":"OUTPUT","value":{"format":"HTML","content":"\u003cp\u003eĐối với mỗi bộ dữ liệu, in ra giả trị 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à vô cùng nhỏ\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"}}]}