#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=20,INF=1<<28;

int dis[MAX][MAX],N;

void floyd(){
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}

int main(){

    int E;cin>>N>>E;
    vector<int> cnt(N);
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            dis[i][j]=INF;
            if(i==j) dis[i][j]=0;
        }
    }
    int sum=0;
    for(int i=0;i<E;i++){
        int a,b,c;cin>>a>>b>>c;
        sum+=c;
        dis[a][b]=min(dis[a][b],c);
        dis[b][a]=min(dis[b][a],c);
        cnt[a]++;
        cnt[b]++;
    }
    
    floyd();
    
    vector<int> S;
    
    for(int i=0;i<N;i++){
        if(cnt[i]%2==1) S.push_back(i);
    }
    
    if(S.size()==0) cout<<sum<<endl;
    else{
        int M=S.size();
        int dp[(1<<M)];
        for(int i=0;i<(1<<M);i++){
            dp[i]=INF;
        }
        dp[0]=0;
        for(int i=0;i<(1<<M);i++){
            for(int j=0;j<M;j++){
                if(i&(1<<j)) continue;
                for(int k=0;k<M;k++){
                    if(i&(1<<k)) continue;
                    if(j==k) continue;
                    dp[i|(1<<j)|(1<<k)]=min(dp[i]+dis[S[j]][S[k]],dp[i|(1<<j)|(1<<k)]);
                }
            }
        }
        
        cout<<sum+dp[(1<<M)-1]<<endl;
        
    }
    
}


