網路設計

內容 ： 

某一城市欲建立都會網路，以使每一區公所均可連線到其他各區公所（可能直接連線或透過其他的區公所間接連線）。假設任兩個區公所之間的佈線成本為已知；每一條網路線均為雙向傳送。請寫一程式，印出哪些區公所之間需要施工佈線，以找出此城市使用最低成本完成此都會網路之佈線架構。

輸入說明 ：

第一列有兩個正整數n及m，其中n代表區公所個數(n<=10)，區公所代碼為W1、W2、W3…Wn。m代表有m個可能的佈線連結兩區公所。其後有m列，每一列之資料依序為兩區公所代碼，及連接此兩區公所之佈線成本。各項資料之間以一個空白分隔；佈線成本為一正整數。

輸出說明 ：

印出二列。第一列為佈線架構，印出數組資料，每一組資料為兩個區公所代碼，代表此兩個區公所需要施工佈線，每一組資料包含在一對括號之中。第二列為佈線總成本。各項資料之間以一個空白分隔。

範例輸入 ：

7 11 

W1 W2 1 

W1 W4 4 

W2 W3 2 

W2 W4 6 

W2 W5 4 

W3 W5 5 

W3 W6 6 

W4 W5 3 

W4 W7 4 

W5 W6 8 

W6 W7 3 

範例輸出 ：

(W1 W2) (W1 W4) (W2 W3) (W4 W5) (W4 W7) (W6 W7) 

17