#include <iostream>
#include <algorithm>
using namespace std;

#define INF 1<<20
#define MAX_V 100

bool done[MAX_V];
int d[MAX_V];
int V;
int cost[MAX_V+1][MAX_V+1];

int dijkstra(int s) {
  int total = 0;
  
  fill(done, done+V, false);
  fill(d, d+V, INF);
  
  d[s] = 0;

  while(1) {
    int v = -1;
    for(int u = 0; u < V; u++) {
      if(!done[u] && ( v == -1 || d[u]<d[v] )) {
	v = u;
      }
    }
    if(v == -1) break;

    done[v] = true;

    for(int u = 0; u < V; u++) {
      d[u] = min(d[u], d[v] + cost[v][u]);
    }
  }

  for(int i=0; i<V; i++) {
    total += d[i];
  }
  
  return total;
}

int main() {
  // テ・ツ、ツ姪」ツ?療」ツ?淌」ツつ嘉ヲツ篠・テァツカツ堙」ツ?古」ツ?ェテ」ツ??ゥツδステ・ツクツづ」ツつ津」ツ?陛」ツ?古」ツ??
  
  int m;
  
  while(cin>>V>>m && (V||m)) {
    
    fill(cost[0], cost[MAX_V], INF);
    
    for(int i=0; i<m; i++) {
      int a, b, cst;
      cin >> a >> b >> cst;
      cost[a][a] = cost[b][b] = 0;
      cost[a][b] = cost[b][a] = cst;
    }

    int res = INF;
    
    for(int i=0; i<V; i++) {
      for(int j=0; j<V; j++) {
	if(i  == j) continue;
	// i <-> j テ・ツ、ツ姪」ツ??
	int temp = cost[i][j];
	cost[i][j] = cost[j][i] = INF;
	
	// テ」ツ?ゥテ」ツ?禿」ツ?ォテ」ツつづァツケツ凝」ツ?古」ツつ嘉」ツ?ェテ」ツ??」ツつ津ァツ「ツコティツェツ?
	int all = 0, cnt = 0;
	for(int k=0; k<V; k++) {
	  all ++;
	  if(cost[i][k] == INF) cnt ++;
	}
	if(all == cnt) { goto lpend; }
	
	all = 0, cnt = 0;
	for(int k=0; k<V; k++) {
	  all ++;
	  if(cost[j][k] == INF) cnt ++;
	}
	if(all == cnt) { goto lpend; }

	/*
	for(int k=0; k<V; k++) {
	  int all = 0, cnt = 0;
	  for(int l=0; l<V; l++) {
	    all ++;
	    // テ」ツ?ゥテ」ツ?禿」ツ?ォテ」ツつづァツケツ凝」ツ?古」ツつ嘉」ツ?ェテ」ツ??」ツつ津ァツ「ツコティツェツ?
	    if(cost[k][l]==INF) cnt ++;
	  }
	  if(all == cnt) {
	    cost[i][j] = cost[j][i] = temp;
	    goto bad;
	  }
	}
	*/
	
	for(int I=0; I<V; I++) {
	  res = min(dijkstra(I), res);
	}
	
      lpend:
	cost[i][j] = cost[j][i] = temp;
      }
    }
    cout << res << endl;
  }
  
  return 0;
}