樹上一位不回家的推銷員 (AP325 Q-8-15)

有一個推銷員要走訪 \(n\) 個城市。這些城市以 \(n-1\) 條道路連接，每條道路連接兩個不同的城市並且雙向可以通行，而且已知每一個城市都可以到達，不會有到達不了的狀況。輸入道路的資料，請你幫推銷員找出一個最短的路徑走訪所有的城市，推銷員可以從任何城市開始，也不必回到開始的城市，只要每個城市至少到一次就可以。

舉例來說，如下圖，有 \(5\) 個城市以 \(4\) 條道路連接，假設每條道路的長度都是 \(1\)。最短的拜訪路徑是 \((1, 0, 4, 2, 4, 3)\)，長度為 \(5\)。

輸入格式

第一行是正整數 \(n\)，代表城市的數量，城市是以 \(0 \sim n-1\) 編號。接下來有 \(n-1\) 行是道路的資料，每行三個整數 \(a\)、\(b\) 與 \(w\)，代表此道路連接城市 \(a\) 與 \(b\)，道路的長度是 \(w\)。同一行的數字以一個空白隔開。

限制

• \(1 \le n \le 50000\)。
• \(0 \le a, b \le n-1\)，\(a \ne b\)；每條道路長度 \(w\) 是不超過 \(100\) 的正整數。
• 保證任兩個城市之間都可以經由道路互相到達。

輸出格式

輸出最短的旅行距離。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

5
1 0 1
0 4 1
2 4 1
4 3 1

範例輸出 1

5

範例輸入 2

3
1 2 5
0 2 3

範例輸出 2

8

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 8 章 Q-8-15，第 311 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。