{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Giống như mọi thành phố hiện đại khác, thành phố **XYZ** có một hệ thống giao thông công cộng rất phát triển. Trái tim của hệ thống giao thông nơi đây chính là tàu điện ngầm. Đặc biệt hệ thống tàu ở đây có hình dạng như một cái cây (đồ thị vô hướng lien thông không chu trình) nếu ta coi các trạm là các đỉnh, các đường ray nối giữa chúng là các cạnh.\n\nBan đầu bản đồ ở đây chứa rất ít thông tin về tàu điện ngầm. Nam được giao nhiệm vụ nâng cấp bằng cách thêm thông tin về thời gian đi lại giữa các cặp ga kề nhau. Nam được nhân viên cung cấp cho các số liệu này, tuy nhiên chúng được ghi lại theo đơn vị là **giây** trong khi bản đồ cần đơn vị là **phút** (lưu ý rằng $1$ phút tương đương với $60$ giây).\n\nMột cách đơn giản để giải quyết vấn đề này là làm tròn các số liệu xuống số phút gần nhất. Tuy nhiên việc này có thể tạo ra một sai số tuyệt đối lớn khi ước tính đường đi giữa hai cặp ga bất kỳ (sai số tuyệt đối bằng với giá trị tuyệt đối của hiệu số liệu chính xác trừ đi số liệu ước tính).\n\nVốn là một người thông minh, Nam đã nghĩ ra giải pháp là thay vì chỉ làm tròn xuống, một số số liệu ta có thể làm tròn lên số phút gần nhất. Vì không giỏi tính toán, hãy giúp Nam tính giá trị nhỏ nhất của sai số lớn nhất giữa hai cặp đỉnh khi thực hiện làm tròn xuống hoặc lên một cách tối ưu.\n\nLưu ý: Ta có thể chứng minh rằng trong bài toán này, kết quả tối ưu không vượt quá $118$."}},{"title":"Input","value":{"format":"MD","content":"Gồm một số dữ liệu, mỗi bộ dữ liệu có dạng như sau:\n- Dòng đầu tiên chứa số nguyên $n$ - số trạm tàu $n\\le 100$.\n- $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a,b,c$ ($c\\le 300$) thể hiện rằng trạm $a$ và $b$ kề với nhau và mất $c$ giây để đi lại giữa chúng.\n\nDữ liệu vào kết thúc bởi một số $0$ trên một dòng."}},{"title":"Output","value":{"format":"MD","content":"Với bộ dữ liệu thứ $i$, in ra **Case i:**, theo sau đó là sai số tuyệt đối nhỏ nhất khi làm tròn một cách tối ưu theo đơn vị là **giây**."}},{"title":"Sample","value":{"format":"MD","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\u003e2\n1 2 110\n4\n1 2 40\n2 3 40\n3 4 40\n4\n1 2 90\n1 3 90\n1 4 90\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 10\nCase 2: 40\nCase 3: 60\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}