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

輸入格式

第一行是正整數 n，代表城市的數量，城市是以 0~n-1 編號， 接下來有 n-1 行是道路的資料，每行三個整數 a,b 與 w，代表此道路連接城市 a 與 b，道路的長度是 w。 n 不超過 50000，每條道路長度是不超過 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