題目 PDF 檔在這裡

眾所皆知，建電社辦有提供 24Hr 免費 Wifi 服務，密碼和某個顏色有關。

然而，有一天，某位學弟把路由器的 WAN 接口插在了 LAN 上，導致對學校內網發送了 DHCP 封包，把學校網路給癱瘓了，因此導致社辦網路被查封 QAQ。在這件事之後，學校不准我們架設 WiFi Router 了。因此，社辦內網路只能回歸以有線網路連接的時代。

為了避免這件事重蹈覆徹，身為建北電資最強學術的你，決定好好的來學習網路管理 (Network Management，簡稱 NA)，並且在社內架設一台新的路由器以及 $n-1$ 台交換機，以應付社辦內部越來越龐大的網路需求（例如鄭向晴的 MC server 等等）。

然而，你正當你跟學長乞討來一批嶄新的交換機之後，你就把它放在社辦，跑去出燒雞考的題目了。於是，你就把架設交換機的工作交給 LAN，並且告訴他要把交換機網路架設好。但是你忘記了 LAN 最近都在忙著約會和三刷 Covid，根本沒時間好好研究交換機怎麼架，因此當你回來的時候，發現這 $n-1$ 台交換機以及路由器之間，被由 $m$ 條網路線胡亂連接在一起了，造成了網路環路 (Network Loop)，進而產生了廣播風暴 (Broadcast Storm)，導致社辦的網路變得非常緩慢，甚至無法使用。

已知，若要解決網路風暴的問題，必須要拔掉一些多餘的網路線，使得從每一台設備（交換機/路由器）出發，到另一台設備，只能有恰好一條路徑。換句話說，拔完網路線之後，必須形成一棵以路由器為根的樹 (Tree)，每一台交換機都為樹上的一個節點，而邊則為沒被拔掉的網路線。

另外，為了使得網路的運作最佳化，我們希望讓每一台設備連到外網的總延遲最小化。已知網路中每個節點 $i$ 有一個延遲 $w_i$，每一條網路線 $(u,v)$ 也有一個延遲 $c_{uv}$。當你從某一台交換機 $u$ 連到外網時，總延遲為從該台交換機連到路由器上，經過的所有網路線的延遲總和，加上路徑當中每一台設備的延遲總和（包含路由器和交換機 $u$ 本身）。因此，請你輸出要留下哪些網路線，才能讓社辦的網路恢復正常運作，並且讓每一台設備連到外網的總延遲最小化。