#include <bits/stdc++.h>
#define N 15
using namespace std;
typedef pair<int,int> P;
int n;
vector<P> G[N];
int g[N][N];
int Min(int &a,int b){return a=min(a,b);}

void WF(){
  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++) Min(g[i][j],g[i][k]+g[k][j]);
}

int mem[1<<N],used[1<<N];
int dfs(int bit){
  if(bit==(1<<n)-1) return 0;
  if(used[bit]++) return mem[bit];

  int res = 1e9;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      if((bit>>i&1) || (bit>>j&1)) continue;
      int nbit = bit | (1<<i) | (1<<j);
      Min(res,g[i][j]+dfs(nbit));
    }
  }
  return mem[bit] = res;
}

int main(){
  int m;
  cin>>n>>m;

  for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) g[i][j] = 1e9;

  int sum = 0;  
  for(int i=0,a,b,d;i<m;i++){
    cin>>a>>b>>d;
    G[a].push_back(P(b,d));
    G[b].push_back(P(a,d));
    Min(g[a][b],d);
    Min(g[b][a],d);
    sum += d;
  } 
  
  int start = 0;
  for(int i=0;i<n;i++)
    if(G[i].size()%2==0) start |= 1<<i;
  WF();

  cout<<sum+dfs(start)<<endl;
  
  
  return 0;
}