AT_pakencamp_2024_day1_r Maximum Water Flow

パ研王国有 $1$ 到 $N$ 编号的 $N$ 个城镇，城镇之间有 $M$ 根水管。第 $i$ 根水管连接城镇 $U_i$ 和 $V_i$，最多可以输送 $W_i$ 单位的水。水可以双向流动。在任意两个城镇之间，最多只有一根水管，并且任意两个城镇之间都可以通过水管互达。 对于任意不同的 $1 \leq i, j \leq N$，记 $f(i, j)$ 为从城镇 $i$ 到城镇 $j$ 最大能够流送的水的量。 请你在所有满足 $P_i \neq i \ (1 \leq i \leq N)$ 的 $1$ 到 $N$ 的排列 $P = (P_1, P_2, \ldots, P_N)$ 中，求 $\displaystyle \sum_{i=1}^{N} f(i, P_i)$ 的最大值。

输入从标准输入读入，格式如下： > $N$ $M$ > $U_1$ $V_1$ $W_1$ > $U_2$ $V_2$ $W_2$ > $\vdots$ > $U_M$ $V_M$ $W_M$

输出答案。

### 样例解释 1 当从城镇 $1$ 向城镇 $2$ 输送水时，可以直接通过 $1$ 到 $2$ 的水管流 $3$ 单位水，也可以经由城镇 $3$ 到 $2$ 的路径输送 $4$ 单位水。这已经是能够流送的最大水量。因此，$f(1,2)=3+4=7$。 当 $P=(3,1,2)$ 时，$f(1,3)+f(2,1)+f(3,2)=7+7+8=22$。无论选取怎样的 $P$，$f(1,P_1)+f(2,P_2)+f(3,P_3)$ 均不会大于 $23$，所以答案为 $22$。 ### 数据范围 - $2 \leq N \leq 100$ - $N-1 \leq M \leq 200$ - $1 \leq U_i, V_i \leq N$，$1 \leq i \leq M$ - $U_i \neq V_i$，$1 \leq i \leq M$ - $1 \leq W_i \leq 10^5$ - 任意两城镇之间最多只有一根水管 - 任意两城镇之间水管连通 - 输入均为整数 由 ChatGPT 5 翻译