//* Problem  : E: Reliable Nets
//* Contest  : ECNA-2005
//* Type     : Solution
//* Date     : 2008.08.04
//* Author   : alt
//* Language : C++
//* Compiler : Microsoft Visual C++ 6.0

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

typedef pair <int,int> PIII;
typedef vector <int> VI;
typedef vector <vector<int> > VVI;
typedef vector <pair<int,int> > VPII;
typedef vector <vector<pair<int,int> > > VVPII;

#define int64 long long
#define PI (2.0 * acos(0.0))
#define MP make_pair
#define PB push_back
#define SZ(a) (int)a.size()
#define FOR(i, n) for (int i = 0; i < (int)n; i++)
#define FORSZ(i, a) FOR(i, SZ(a))
#define FORE(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(a); i >= int(b); i--)
#define INF 1000000000
#define INFL 1000000000000000000LL
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()

inline int si(){int tt; scanf("%d", &tt); return tt;}

int n, m, res;

int x[20], y[20], c[20];

int dp[1<<20];

int vis[20];

int dfs(int v, int mask)
{
	if (vis[v]) return 0;
	int res = vis[v] = 1;
	FOR(i, m)
		if (mask & (1<<i))
		if (x[i] == v)
			res += dfs(y[i], mask);
		else if (y[i] == v)
			res += dfs(x[i], mask);
	return res;
}

inline int connected(int mask)
{
	memset(vis, 0, sizeof(vis));
	return dfs(1, mask) == n;
}

inline int check(int mask)
{
	int res = 0;
	FOR(i, m)
		if (mask & (1<<i))
		{
			res += c[i];
			if (!connected(mask - (1<<i))) return INF;
		}
	return res;
}

int solve(int mask)
{
	if (!dp[mask])
	{
		int res = INF;
		if ((res = check(mask)) != INF)
			FOR(i, m)
				if (mask & (1<<i))
					res = min(res, solve(mask - (1<<i)));
		dp[mask] = res + 1;
	}
	return dp[mask] - 1;
}

int main()
{
#ifdef _DEBUG
	freopen("1064", "r", stdin);
//	freopen("1064w", "w", stdout);
#endif
	int it = 0;
	while (scanf("%d%d", &n, &m) == 2 && n)
	{
		memset(dp, 0, sizeof(dp));
		dp[0] = INF + 1;
		it++;
		FOR(i, m)
			x[i] = si(), y[i] = si(), c[i] = si();
		res = solve((1<<m) - 1);
		if (res != INF)
			printf("The minimal cost for test case %d is %d.\n", it, res);
		else
			printf("There is no reliable net possible for test case %d.\n", it);
	}
	return 0;
}

