三秒前，你被小 Y 跟小 P 的爭吵聲吵醒。所以經過了漫⻑三秒鐘的思考，你決定解決他們遇到的問題。

強者 小Y 與小 P 已經學會了 $N$ 個技能，但是在不同的技能之間，常常無法順暢的轉換，為此他們訂定了各種訓練計畫以及計算好了各種訓練所需的時間，希望能將N個技能都融會貫通。現在小 Y 與小 P 手上拿著一張由 $N$ 個點 $M$ 條邊組成的技能圖，每個點可以對應到一個不同的技能，技能分別從 $1$ 編號到 $N$，而每一條邊的兩端都連接著不同編號的點，保證圖上不存在兩條邊連接相同的點對。圖上的第 $i$ 條邊連接著兩個技能點 $A_i$ 與 $B_i$，且另外寫了一個邊權 $V_i$，$V_i$ 代表將技能 $A_i$ 與技能 $B_i$ 融會貫通的時間。

現在小 Y 和小 P 希望能透過選擇一些邊使得任兩個技能都融會貫通。正式的說，兩種不同的技能 $A$ 與技能 $B$ 能融會貫通需至少滿足以任下一個情況：

1. 存在一條被選擇的邊連接著技能 $A$ 和技能 $B$。

2. 存在一個與技能 $A$ 和技能 $B$ 皆不相同的技能 $C$，使得技能 $A$ 與技能 $C$ 能融會貫通且技能 $B$ 與技能 $C$ 能融會貫通。

小 Y 和小 P 在通過⻑期的觀察後發現，只需要適當的選擇恰好 $N-1$ 條邊就可以將所有的技能兩兩都融會貫通，而將所有技能融會貫通的總時間就是選擇的所有邊權總和！但是對於要選擇哪些邊，兩人卻發生了意見分歧，小 Y 希望透過最少的時間將所有技能融會貫通顯示自己天賦異稟，但是小 P 卻希望透過最多的時間將所有技能融會貫通顯示自己刻苦耐勞。

在了解事情的始末而為了能趕快回到夢鄉的你，決定用最少的修改次數偷偷修改技能圖上的邊權，每一次修改都可以選擇圖上的任一條邊並重新將邊權指定成任意的非負整數，使最後融會貫通所有的題目的總時間，不論是採用小 Y 的方案還是小 P 的方案都是相同的。