#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>#include<algorithm> using namespace std; const int MAXN = 17, INF = 1<<29; int n, m, t1, t2, t3, ans, mp[MAXN][MAXN], deg[MAXN], u[MAXN];int dfs();int dfs(){int i, j, rnt=INF;for(i=0; i<n; i++) if(!u[i]) break;if(i == n) return 0;u[i] = 1;for(j=i+1; j<n; j++) if(!u[j]) u[j]=1, rnt=min(rnt,dfs()+mp[i][j]), u[j]=0;u[i] = 0;return rnt;}int main(){while(scanf("%d",&n),n){ scanf("%d",&m), ans=0, memset(deg,0,sizeof(deg)), memset(u,0,sizeof(u)); for(int i=0; i<n; i++) for(int j=0; j<n; j++) mp[i][j]=INF; for(int i=0; i<m; i++) { scanf("%d%d%d",&t1,&t2,&t3); t1--, t2--, ans+=t3, deg[t1]++, deg[t2]++; mp[t1][t2] = mp[t2][t1] = min(mp[t1][t2],t3); } for(int k=0; k<n; k++) for(int i=0; i<n; i++) for(int j=0; j<n; j++) mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j]); for(int i=0; i<n; i++) if(deg[i]%2 == 0) u[i] = 1; printf("%dn", ans+dfs());}return 0; }
