#include<bits/stdc++.h>
using namespace std;
#define MAX_V 20
#define INF 2000000001
int d[MAX_V][MAX_V];
int V;
int edge[20];

void init(){
  for(int i=0;i<V;i++)
    for(int j=0;j<V;j++)
      if(i==j)d[i][j]=0;
      else d[i][j]=INF;
} 

void warshall_floyd(){
  for(int k=0;k<V;k++)
    for(int i=0;i<V;i++)
      for(int j=0;j<V;j++)
	if(d[i][k]!=INF&&d[k][j]!=INF)
	  d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

int sum=INF;
int dp[1<<20];
vector<int> v;

int rec(int s=0){
  if(dp[s]>=0)return dp[s];
  if(s==(1<<v.size())-1)return 0;
  int res=INF;
  for(int i=0;i<v.size();i++){
    if(s>>i&1)continue;
    for(int j=0;j<v.size();j++){
      if(s>>j&1)continue;
      if(i==j)continue;
      res=min(res,rec((s|1<<i)|1<<j)+d[v[i]][v[j]]);
    }
  }
  return dp[s]=res;
}

int main(){
  int E,ans=0;
  cin>>V>>E;
  init();
  for(int i=0;i<E;i++){
    int s,t,k;
    cin>>s>>t>>k;
    edge[s]++,edge[t]++;
    d[s][t]=min(k,d[s][t]);
    d[t][s]=d[s][t];
    ans+=k;
  }
  warshall_floyd();
  memset(dp,-1,sizeof(dp));
  for(int i=0;i<V;i++)
    if(edge[i]%2)v.push_back(i);
  cout<<rec()+ans<<endl;
  return 0;
}
