Thành phố nọ gồm ngôi làng và các ngôi làng được nối với nhau dạng cây, nghĩa là có con đường nối một số ngôi làng với nhau sao cho giữa ngôi làng bất kì đều có một đường đi qua các con đường giữa chúng. Có thành viên của đội tình nguyện đang ở ngôi làng trung tâm của thành phố và họ đang rất mệt mỏi sau một ngày làm việc. Bạn là tài xế, và bạn đang muốn chở họ về nhà nhanh nhất có thể. Bạn sẽ chở tất cả mọi người ở trên xe, đi tới từng nhà của từng người một. Có người trong đội tình nguyện, nhà của họ đều nằm trong các làng, và không có ai cùng làng cả. Khi chở người cuối cùng tới nhà, bạn sẽ ở lại đó luôn qua đêm.
Tuy biết địa chỉ nhà của từng người, nhưng bạn phải quyết định xem thứ tự chở mọi người thế nào là nhanh nhất. Thêm vào đó, bạn không hề biết trung tâm thành phố ở đâu. Nhiệm vụ của bạn là với mỗi một thành phố, giả sử đó là trung tâm thành phố thì bạn cần ít nhất bao nhiêu thời gian để thực hiện lộ trình trên.
Dữ liệu vào:
Dòng đầu là số và là số làng và số người cần về nhà ;
dòng sau mỗi dòng ghi ba số , nghĩa là có đường nối giữa làng và làng với thời gian đi qua là ;
dòng tiếp theo, mỗi dòng ghi một số là địa chỉ nhà của một người trong đội tình nguyện.
Dữ liệu ra:
Gồm dòng, dòng thứ là thời gian nhanh nhất của lộ trình nếu thành phố là thành phố trung tâm.
