{"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePavel chơi một trò chơi máy tính nổi tiếng. Một người chơi chịu trách nhiệm cho một quốc gia và anh ta có thể di chuyển tự do, hoàn thành nhiệm vụ và kiếm kinh nghiệm.\u003c/p\u003e\u003cp\u003eQuốc gia này có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e thành phố được kết nối bởi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e con đường hai chiều có độ dài khác nhau, sao cho có thể đi từ một thành phố này đến bất kỳ thành phố khác. Có cổng trong \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e trong số những thành phố này. Ở đầu trò chơi, tất cả cổng đều đóng. Khi một người chơi đến một thành phố có cổng, cổng mở ra. Lạ thay, người ta có thể di chuyển từ một cổng mở ra đến một cổng khác mở ra. Việc di chuyển này không tốn thời gian và cho phép người chơi di chuyển nhanh chóng giữa các vùng xa xôi của quốc gia.\u003c/p\u003e\u003cp\u003eỞ đầu trò chơi, Pavel ở thành phố số \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. Anh ấy muốn mở tất cả cổng càng nhanh càng tốt. Anh ấy cần bao lâu để làm điều đó?\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách \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\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) cho biết có bao nhiêu thành phố và con đường trong trò chơi.\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 mô tả của một con đường với ba số nguyên cách nhau bởi dấu cách \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003ey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e) — số của các thành phố được kết nối bởi con đường thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e và thời gian cần thiết để đi từ một thành phố này đến thành phố khác bằng con đường này. Bất kỳ hai thành phố nào cũng được kết nối bởi không quá một con đường. Đảm bảo rằng chúng ta có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố khác, di chuyển theo các con đường của quốc gia.\u003c/p\u003e\u003cp\u003eDòng tiếp theo chứa số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — số lượng cổng.\u003c/p\u003e\u003cp\u003eDòng tiếp theo chứa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e số nguyên cách nhau bởi dấu cách \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e, ..., \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e — số của các thành phố có cài đặt cổng. Mỗi thành phố không có nhiều hơn một cổng.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn ra một số duy nhất — thời gian tối thiểu mà một người chơi cần để mở tất cả cổng.\u003c/p\u003e\u003cp\u003eVui lòng không sử dụng bộ định dạng \u003cspan class\u003d\"tex-font-style-tt\"\u003e%lld\u003c/span\u003e để đọc hoặc viết số nguyên 64-bit trong C++. Nên sử dụng luồng \u003cspan class\u003d\"tex-font-style-tt\"\u003ecin\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003ecout\u003c/span\u003e hoặc bộ định dạng \u003cspan class\u003d\"tex-font-style-tt\"\u003e%I64d\u003c/span\u003e.\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 3\n1 2 1\n1 3 1\n2 3 1\n3\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 2","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\u003e4 3\n1 2 1\n2 3 5\n2 4 10\n3\n2 3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ví dụ 3","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\u003e4 3\n1 2 1000000000\n2 3 1000000000\n3 4 1000000000\n4\n1 2 3 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ thứ hai, người chơi phải đến thành phố \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, mở cổng ở đó, sau đó đi đến thành phố \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, mở cổng ở đó, di chuyển ngược lại thành phố \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e và cuối cùng hoàn thành hành trình ở thành phố \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e.\u003c/p\u003e"}}]}