市政府派出一輛洗街車欲清洗甲區域的街道，甲區域有 N 個加水站，2 <= N <= 1500。為了方便說明，我們將 N 個加水站名稱以正整數 1, 2, …, N 來表示。N 個加水站有街道來連接，使得洗街車可從任一個加水站出發，經由幾條街道抵達另一個加水站。我們可以用圖形來表示這些加水站跟街道的關係：節點表示加水站；而連接結點的連結線則代表連接兩個加水站之間的街道。我們以符號 (I, J) 來表示連接加水站 I 和加水站 J 的連結線，並稱街道 (I, J) 與加水站 I 和加水站 J 相接。每一條連結線 (I, J) 都結合一個權重 w(I, J) 來代表清洗 (I, J) 這條街道所要花費的時間，w(I, J) 為正整數滿足 1 <= w(I, J) <= 888。圖一有 12 個加水站，以數字1 ~ 12 來表示，而街道上的數字則代表清洗此街道所需花費的時間。令 N_odd 代表那些與奇數條街道相接的加水站個數，則甲區域有一個重要特性：N_odd 為偶數且0 <= N_odd <= 14 。在圖一的例子中，N_odd = 8 ，起始加水站為 1。
　　給定一個起始加水站，請寫一個程式計算洗街車從起始加水站出發，把每條街道都清洗過至少一次，再回到原起始加水站所需花費的最短時間為何？注意：這個城市中所有的街道都是雙向道，洗街車洗街時同一個加水站和街道可被洗街車重複經過。

圖二說明其中一種走法為：1 → 8 → 1 → 9 → 8 一7 → 12 → 6 → 7 → 6 → 5 → 4 → 5 → 11 → 12 → 9 → 10 → 11 → 4 → 3 → 2 → 3 → 10 → 2 → 1，可在 73 單位時間將所有街道都清洗過至少一次，然而此種走法所需的時間並非最短。事實上，此例中花費時間為最短的走法如圖三所示為 l → 8 → 9 → 1 → 9 一8 → 7 → 6 → 12 → 7 → 12 → 6 → 5 → 4 → 11 → 5 → 11 → 4 → 3 → 2 → 10 → 3 → 10 → 11 → 12 → 9 → 10 → 2 → l，所花費時間為 64 單位。