問題文

パ研王国には 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) の最大値を求めてください。

制約

• 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 つの町の間は水道管を通って到達可能
• 入力は全て整数

入力例 1

3 3
1 2 3
2 3 5
1 3 4

出力例 1

22

町 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 です。

入力例 2

5 10
1 3 36426
4 3 90081
3 5 3497
2 1 68417
5 1 35902
2 4 23857
5 2 29211
3 2 63340
5 4 60016
1 4 24593

出力例 2

820246