#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
#define int long long
int n,a[20],p[100][100],ans=1e9,xx[101],m;
int dfs(int d,int pp){
  if(d==m){
    int p=0,t=0;
    for(int i=1;i<=n;i++){
      if(a[i]%2)p++;
      t+=a[i];
    }
    if(p<3&&t/2==n)ans=min(pp,ans);
  }else{
    dfs(d+1,pp);
    a[p[d][0]]--;
    a[p[d][1]]--;
    dfs(d+1,pp+xx[d]);
    a[p[d][0]]++;
    a[p[d][1]]++;
  }
}
main(){
  cin>>n>>m;
  r(i,m){
    cin>>p[i][0]>>p[i][1]>>xx[i];
    a[p[i][0]]++;
    a[p[i][1]]++;
  }
  dfs(0,0);
  cout<<ans<<endl;
}