AT_pakencamp_2024_day1_r Maximum Water Flow

パ研王国には $ 1 $ から $ N $ までの番号が付けられた $ N $ 個の町と町の間をつなぐ水道管が $ M $ 本あります。 $ i $ 本目の水道管は町 $ U_i $ と $ V_i $ の間を結び、最大で水を $ W_i $ だけ流すことができます。また、水道管はどちらの方向にも流すことができます。任意の $ 2 $ つの町の間には高々 $ 1 $ 本の水道管が通っており、任意の $ 2 $ つの町の間は水道管を通って到達可能です。 $ 1 $ 以上 $ N $ 以下の異なる $ 2 $ つの整数 $ i,j $ について、 $ f(i,j) $ を町 $ i $ から町 $ j $ へ流せる水の量の最大値とします。 このとき、 $ (1,2,\ldots,N) $ の順列 $ P=(P_1,P_2,\ldots ,P_N) $ のうち、すべての $ 1 $ 以上 $ N $ 以下の整数 $ i $ について $ P_i \neq i $ を満たすものについて $ \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 $

答えを出力せよ。

### Sample Explanation 1 町 $ 1 $ から町 $ 2 $ へ水を流すとき、 町 $ 1 $ から町 $ 2 $ への水道管で水を $ 3 $ 流すことができ、町 $ 1 $ から 町 $ 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 $ です。 ### Constraints - $ 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 $ - 任意の $ 2 $ つの町の間には高々 $ 1 $ 本の水道管が通っている - 任意の $ 2 $ つの町の間は水道管を通って到達可能 - 入力は全て整数