#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,S=(<<)+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,u,v,w,d[N][N],de[N];

void floyd(){

    for(int k=;k<=n;k++)

        for(int i=;i<=n;i++) if(d[i][k]<INF)

            for(int j=;j<=n;j++)

                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

}

int a[N],p,f[S];

void dp(){

    //for(int i=1;i<=p;i++) printf("a %d\n",a[i]);

    memset(f,0x3f,sizeof(f));

    f[]=;

    int All=<<p;

    for(int s=;s<All;s++){

        int i=;

        while((<<i)&s) i++;

        for(int j=i+;j<p;j++) if( !((<<j)&s) )

            f[s|(<<i)|(<<j)]=min(f[s|(<<i)|(<<j)],f[s]+d[a[i]][a[j]]);

    }

}

int main(){

    freopen("in","r",stdin);

    while( (n=read()) ){

        m=read();

        for(int i=;i<=n;i++){

            de[i]=;

            for(int j=;j<=n;j++) if(i!=j) d[i][j]=INF;

        }

        int sum=;

        for(int i=;i<=m;i++){

            u=read(),v=read(),w=read();

            d[u][v]=d[v][u]=min(d[u][v],w); sum+=w;

            de[u]++;de[v]++;

        }

        p=;

        for(int i=;i<=n;i++) if(de[i]&) {a[p++]=i;}

        if(!p) {printf("%d\n",sum);continue;}

        floyd();

        dp();

        printf("%d\n",sum+f[(<<p)-]);

    }

}