#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<algorithm>
using namespace std;

#define ll long long

//#define flow(from,to) (f[from][to] - f[to][from])
//#define residue(from,to) (cap[from][to] - flow(from,to))
/*
int cap[512][512];
int cost[512][512];
int f[512][512];
typedef int V;


int d[512][512];
int dr[512][512];
int buf[512][512];
*/

typedef int V;
typedef int COST;

#define E 0.000000001
class edge{
public:
	int i, j;
	V cap;
	COST cost2;
	V flow;
	int dest( int from){
		if( i == from )
			return j;
		else
			return i;
	}
	V    residue(int from){
		if( i == from )
			return cap - flow;
		else
			return flow;
	}
	COST cost(int from){
		if( i == from )
			return cost2;
		else
			return - cost2;
	}
	void flow_add( int from, V r ){
		if( i == from )
			flow += r;
		else
			flow -= r;
	}
};

vector<edge> e(30000);
// pair<int, int>, pair<int, double>
V
get_max_flow( 
int n,
int s, int t,
vector< vector< int > > &adj
)
{
	vector< COST > p( n, 0 );
	// flow/potential at equibilium

	vector< COST > d(n);
	vector< pair<int, int> > prev(n);
	vector< int > visited(n);

	V flow_sum = 0;

	while( 1 ){ // until the flow becomes feasible
//		printf( "auau1\n" );

		// dij
		priority_queue< pair<COST, int> > wl;
		for( int i = 0; i < n; i ++ ){
			prev[i].second = -1;
			visited[i] = 0;
			d[i] = -1;
		}
		wl.push( pair<COST, int>( -0, s ) );
		d[s] = 0;

		while( !wl.empty() ){
			int i   =   wl.top().second;
			COST di = - wl.top().first;
			wl.pop();
			if( visited[i] )
				continue;
//			printf( "visit %d\n", i );
			visited[i] = 1;

			for( int J = 0; J < adj[i].size(); J ++ ){
				int eid = adj[i][J];
//				printf( "%d -> %d\n", i, e[J].j );
				if( e[eid].residue(i) <= E )
					continue;
				int j = e[eid].dest(i);
				COST dj = di + e[eid].cost(i) + p[i] - p[j];
				dj = max( dj, di );
				if( d[j] < 0 || d[j] - E > dj ){
					wl.push( pair<COST, int>( -dj, j ) );
					d[j] = dj;
					prev[j] = pair<int,int>(eid, i);
				}
			}
		} // dij end

//		printf( "auau 2 %d\n", flow_sum );

		if( d[t] < 0 ) return flow_sum; // done!

//		printf( "auau3\n" );

		for( int i = 0; i < n; i ++ )
			if( d[i] >= 0 )
				p[i] += d[i];

		V r = 2;
		for( int i = t; prev[i].second >= 0; i = prev[i].second ){
			V res = e[prev[i].first].residue(prev[i].second);
			r = min( r, res );
		}
//		printf( "auau5 r = %d\n", r );
		if( r > 0 ){
			for( int i = t; prev[i].second >= 0; i = prev[i].second ){
//				printf( "%d -> %d\n", prev[i].second, i );
				e[prev[i].first].flow_add(prev[i].second, r );
			}
			flow_sum += r;
		}
	}
}


int main( void )
{
	FILE *in = fopen( "path.in", "r" );

	for( int C = 1; ; C ++ ){
		int N, M;
		fscanf( in, "%d%d", &N, &M );
		if( N == 0 && M == 0 )
			break;
		int N2 = N + M + 2;
		vector< vector< int > > adj( N + 2 );
		int eid = 0;
		for( int i = 0; i < M; i ++ ){
			int a, b, cost;
			fscanf( in, "%d%d%d", &a, &b, &cost );
			e[eid].i = a + 2;
			e[eid].j = b + 2;
			e[eid].cap = 1;
			e[eid].cost2 = cost;
			e[eid].flow = 0;
			adj[a+2].push_back( eid );
			adj[b+2].push_back( eid );
			eid ++;
		}

		e[eid].i = 0;
		e[eid].j = 2;
		e[eid].cap = 2;
		e[eid].cost2 = 0;
		e[eid].flow = 0;
		adj[0].push_back( eid );
		adj[2].push_back( eid );
		eid ++;

		e[eid].i = N + 1;
		e[eid].j = 1;
		e[eid].cap = 2;
		e[eid].cost2 = 0;
		e[eid].flow = 0;
		adj[N + 1].push_back( eid );
		adj[1].push_back( eid );
		eid ++;

		printf( "Instance #%d: ", C );
		if( get_max_flow( N + 2, 0, 1, adj ) != 2 ){
			printf( "Not possible\n" );
		}
		else{
			double d = 0;
			for( int i = 0; i < eid; i ++ ){
				d += e[i].cost2 * e[i].flow;
			}
			printf( "%d\n", (int)d );
		}
	}
	return 0;
}