{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Quốc đảo Flatopia hoàn toàn phẳng. Thật không may, Flatopia không có đường cao tốc công cộng. Vì vậy, giao thông rất khó khăn ở Flatopia. Chính phủ Flatopia nhận thức được vấn đề này. Họ đang kế hoạch xây dựng một số con đường cao tốc để có thể lái xe giữa bất kỳ cặp thị trấn nào mà không cần rời khỏi hệ thống đường cao tốc. \n\nCác thị trấn Flatopia được đánh số từ 1 đến N. Mỗi con đường cao tốc kết nối chính xác hai thị trấn. Tất cả các con đường cao tốc đi thẳng. Tất cả các con đường cao tốc có thể được sử dụng ở cả hai hướng. Các con đường cao tốc có thể tự do giao nhau, nhưng người lái xe chỉ có thể chuyển đổi giữa các con đường cao tốc tại một thị trấn nằm ở cuối của cả hai con đường cao tốc. \n\nChính phủ Flatopia muốn giảm thiểu độ dài của con đường cao tốc dài nhất cần phải xây dựng. Tuy nhiên, họ muốn đảm bảo rằng mọi thị trấn đều có thể đến từ mọi thị trấn khác thông qua đường cao tốc."}},{"title":"Nhập","value":{"format":"HTML","content":"Dòng đầu tiên của đầu vào là một số nguyên T, cho biết có bao nhiêu trường hợp kiểm tra tiếp theo. \n\nDòng đầu tiên của mỗi trường hợp là một số nguyên N (3 \u0026lt;\u003d N \u0026lt;\u003d 500), đó là số lượng làng. Sau đó là N dòng, dòng thứ i chứa N số nguyên, và số thứ j trong N số nguyên này là khoảng cách (khoảng cách phải là số nguyên trong khoảng [1, 65536]) giữa làng i và làng j. Có một dòng trống sau mỗi trường hợp kiểm tra."}},{"title":"Đầu ra","value":{"format":"HTML","content":"Đối với mỗi trường hợp kiểm tra, bạn nên đưa ra một dòng chứa một số nguyên, đó là độ dài của con đường dài nhất cần phải xây dựng sao cho tất cả các làng được kết nối, và giá trị này là tối thiểu."}},{"title":"Ví dụ","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\u003e1\r\n\r\n3\r\n0 990 692\r\n990 0 179\r\n692 179 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e692\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Gợi ý","value":{"format":"HTML","content":"Đầu vào lớn, nên sử dụng scanf."}}]}