a273. TOI 2022/10 潛力組：資料中心

題目描述

N 個資料中心由 M 條雙向連線連成一個連通網路，每條連線都有流量上限。現在要停用部分連線，使任意兩個資料中心之間恰有一條路徑。

簡化後，兩個中心間的傳輸流量受到它們路徑上最小流量上限的限制；整個網路的保證流量，則是所有兩中心組合中最小的這個數值。請選擇保留哪些連線，讓簡化後的保證流量最大。

輸入格式

第一行輸入 N、M，3 ≤ N ≤ 10000，1 ≤ M ≤ 100000。 接下來 M 行各有 S、T、F，表示 S 與 T 間的雙向連線流量上限為 F，其中 1 ≤ S < T ≤ N，1 ≤ F ≤ 1000000000。 兩個中心間至多一條連線，原始網路保證連通。

輸出格式

輸出網路簡化後，保證流量的最大可能值。

來源

TOI 2022 年 10 月潛力組〈資料中心〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202210/Center.pdf