// Solution to "Reliable Nets" by Bob Roos
//
// A few notes to guide my own thinking as I work on this...
// We are looking for a minimum-weight subgraph that is "2-edge-connected."
// Another way of saying this is that the graph is connected and
// has no "bridges":
//
//     o---o------------o---o
//      \ /    bridge    \ /
//       o                o
//
// Note that the subgraph may not be biconnected (i.e., "2-vertex-connected");
// the following is a reliable network but is not biconnected:
//
//    o---o---o
//     \ / \ /
//      o   o
//
// Tarjan published an algorithm to test for the presence of bridges
// in "A note on finding the bridges of a graph." Inform. Process. Lett. 2
// (1973) 160-161, but it's not yet clear to me if I need to do this.
// A node is an endpoint of a bridge if its "lowpoint" (as defined in the
// algorithm for biconnected components) is equal to its own DFS number.
//
// Note that the minimum weight reliable subgraph needn't have a minimum
// number of edges among all such reliable subgraphs, e.g.,
//
//        3     3
//      -----o------
//     /   1/|      \
//    o    o |1      o  Original graph
//    |\   1\|      /|
//    | -----o------ |
//    |   1     1    |
//     \____________/
//           1
//
//        3
//      -----o
//     /   1/           5 edges; weight 7
//    o    o         o
//    |    1\       /|
//    |      o------ |
//    |   1     1    |
//     \____________/
//           1
//
//
//           o
//         1/|          6 edges; weight 6
//    o    o |1      o
//    |\   1\|      /|
//    | -----o------ |
//    |   1     1    |
//     \____________/
//           1

import java.io.*;
import java.util.*;

public class Reliable {

  public static final int MAXNODES = 15;

  public static class Pair {
    public Integer i,w;
    public Pair(Integer i, Integer w) {
//      this.i = new Integer(i);
//      this.w = new Integer(w);
      this.i = i;
      this.w = w;
    }
  }

  public static class Edge {
    public Integer i,w,j;

    public Edge(Integer i, Integer w, Integer j) {
//      this.i = new Integer(i);
//      this.w = new Integer(w);
//      this.j = new Integer(j);
      this.i = i;
      this.w = w;
      this.j = j;
    }
  }

  public static class Node {
    public Vector nbr;

    public Node() {
      nbr = new Vector();
    }

    public int geti(int i) {
      return ((Pair)nbr.get(i)).i.intValue();
    }

    public int getw(int i) {
      return ((Pair)nbr.get(i)).w.intValue();
    }

    public void add(int i, int w) {
      nbr.add(new Pair(new Integer(i),new Integer(w)));
    }

    public int size() {
      return nbr.size();
    }

    public void remove(int v) {
      for (int i = 0;i < nbr.size(); i++) {
        Pair temp = (Pair)(nbr.get(i));
        if (temp.i.intValue() == v) {
          nbr.remove(i);
          break;
        }
      }
    }
  }

  public static BufferedReader in;
  public static StringTokenizer tok;
  public static String line;
  public static int n,m; // number of vertices, number of edges
  public static int casenum;
  public static Node[] graph;
  public static Node[] newgraph;
  public static Vector edgeList;
  public static int dfs[];
  public static int lowpt[];
  public static int dfsNum;
  public static int minWeight,bestMinWeight;

  public static void main(String[] args) throws IOException {

/*DEBUGGING -- CATCH CTRL-C to check progress on long computations:
Runtime.getRuntime().addShutdownHook(new Thread()
{
    public void run()
    {
System.out.println("CTRL-C -- bestMinWeight = " + bestMinWeight);
    }
});
*/
    in = new BufferedReader(new InputStreamReader(System.in));
    casenum = 0;
    while ((line = in.readLine().trim()) != null) {
      tok = new StringTokenizer(line);
      n = Integer.parseInt(tok.nextToken());
      if (n == 0)
        break;
      casenum++;
      m = Integer.parseInt(tok.nextToken());
      graph = new Node[n];
      for (int i = 0; i < n; i++)
        graph[i] = new Node();
      newgraph = new Node[n];
      for (int i = 0; i < n; i++)
        newgraph[i] = new Node();

      edgeList = new Vector();
     // Read in m lines, each with one link in the graph

      for (int i = 0; i < m; i++) {
        line = in.readLine().trim();
        tok = new StringTokenizer(line);
        int b1 = Integer.parseInt(tok.nextToken());
        int b2 = Integer.parseInt(tok.nextToken());
        int c = Integer.parseInt(tok.nextToken());
        bestMinWeight += c;
        graph[b1-1].add(b2-1,c);
        graph[b2-1].add(b1-1,c);
        if (b1 < b2) // not sure why I bothered to order these!
          edgeList.add(new Edge(new Integer(b1-1),new Integer(c),new Integer(b2-1)));
        else
          edgeList.add(new Edge(new Integer(b2-1),new Integer(c),new Integer(b1-1)));
      }

     // Processing starts here:
      minWeight = 0;
      int answer = process();
      if (answer < 0)
        System.out.println("There is no reliable net possible for test case "
           + casenum+".");
      else
        System.out.println("The minimal cost for test case " + casenum + " is "
           + answer+".");
    }
  }


  // Driver method for finding min. reliable subnet:

  public static int process() {
    // First do the easy base case -- initial graph is already unreliable:
    if (!reliable(graph))
      return -1;

    // Sort the edgelist so lower-weight edges get tried first:
    for (int i = 1; i < edgeList.size(); i++) {
      Edge temp = (Edge)(edgeList.get(i));
      int w = temp.w.intValue();
      int j = i-1;
      while (j >= 0 && ((Edge)(edgeList.get(j))).w.intValue() > w) {
        edgeList.setElementAt(edgeList.get(j),j+1);
        j--;
      }
      edgeList.setElementAt(temp,j+1);
    }

    for (int i = 0; i < edgeList.size(); i++) {
       recurAdd(i);
    }

    return bestMinWeight;
  }


  public static void recurAdd(int e) {
    Edge t = (Edge)(edgeList.get(e));
    int v = t.i.intValue();
    int wt = t.w.intValue();
    int w = t.j.intValue();
//System.out.println("Adding " + (v+1) + "---"+wt+"--- "+(w+1));
    newgraph[v].add(w,wt);
    newgraph[w].add(v,wt);
//printGraph(newgraph);
    minWeight += wt;
    if (minWeight >= bestMinWeight) { // no point continuing
//System.out.println("Giving up since minWeight ("+minWeight+
//") >= bestMinWeight ("+bestMinWeight+")");
      newgraph[v].remove(w);
      newgraph[w].remove(v);
      minWeight -= wt;
//System.out.println("Removing " + (v+1) + "---"+wt+"--- "+(w+1));
      return;
    }
    if (reliable(newgraph)) {
      if (minWeight < bestMinWeight) {
        bestMinWeight = minWeight;
//System.out.println("updating bestMinWeight to " + bestMinWeight);
      }
//System.out.println("Reliable! minWeight = " + minWeight +
//", bestMinWeight = " + bestMinWeight);
      newgraph[v].remove(w);
      newgraph[w].remove(v);
      minWeight -= wt;
//System.out.println("Removing " + (v+1) + "---"+wt+"--- "+(w+1));
      return;
    }
    else {
      for (int i = e+1; i < edgeList.size(); i++)
           recurAdd(i);
    }
    newgraph[v].remove(w);
    newgraph[w].remove(v);
    minWeight -= wt;
  }

  // Returns true if and only if the current graph is reliable:
  public static boolean reliable(Node[] graph) {
    dfs = new int[n]; // dfs numbers assigned to vertices
    lowpt = new int[n]; // lowpt (from biconnected component alg)

    for (int i = 0; i < n; i++) // initially, no vertices visited
      dfs[i] = -1;

    Node v = graph[0];
    boolean ok = true;
    dfsNum = 0;
    dfs[0] = dfsNum++;
    for (int i = 0; i < v.size(); i++) { // visit all neighbors of node 0
      int wi = v.geti(i);
      if (dfs[wi] < 0) // happens only if network isn't 2-vertex-connected,
                       // but we have to keep going since it could still be
                       // 2-edge-connected
        ok = ok && search(0,wi,graph);
    }
/* DEBUG:
System.out.println("dfs["+0+"] = "+dfs[0]);
System.out.println("lowpt["+0+"] = "+lowpt[0]);
*/
    return (ok && dfsNum == n); // if != n, graph is disconnected
  }



  // Depth-first search to check for bridges:
  public static boolean search(int parent, int v, Node[] graph) {

// System.out.println("Entering " + v);
    dfs[v] = dfsNum++;
// System.out.println("dfs["+v+"] = "+dfs[v]);
    lowpt[v] = dfs[v];
    Node w = graph[v];

    // For each neighbor of the newly-visited node:
    for (int i = 0; i < w.size(); i++) {
      int wi = w.geti(i);
      if (dfs[wi] >= 0) { // neighbor has already been visited in the dfs
        if (wi != parent) // not parent, must be back edge -- check lowpt:
          lowpt[v] = Math.min(lowpt[v],dfs[wi]);
      }
      else if (!search(v,wi,graph)) // wi never visited, so recursively search wi
          return false;
      else
        lowpt[v] = Math.min(lowpt[v],lowpt[wi]);
    }
    return ((dfs[v] != lowpt[v])); // equality indicates a bridge endpoint
  }

  // Strictly for debugging purposes:
  public static void printGraph(Node[] graph) {
    for (int i = 0; i < n; i++) {
      System.out.print((i+1)+": ");
      for (int j = 0; j < graph[i].nbr.size(); j++) {
        Pair x = (Pair)(graph[i].nbr.get(j));
        System.out.print(" "+(1+x.i.intValue()));
      }
      System.out.println();
    }
  }
}

