#include <iostream>
#include <algorithm>
using namespace std;
struct Node{
	int s,d;
	_int64 c;
};
struct Fun{
	int s, num;
};
struct Way{
	_int64 total_cost;
	int node[70];
	int num_node;
};
Way way[10010]; 
Node d[10010];
Fun f[70]; _int64 N,M,W;
void Next( int *v,int v_n, int *node, int n_n, int cur_v) 
{
      int p = f [cur_v ].s;
	  int n = f [cur_v ].num; 
	  for(int i=0;i<n;i++){
		  if ( d[p].d == cur_v){ 
			  p++; continue;   }
          if ( d[p].d == N-1 )  
		  {
              way[W].num_node = n_n+1;  
			  way[W].total_cost = 0;
			  for(int j=0;j<n_n;j++){  
                   way[W].node[j] = node[j];
                   way[W].total_cost += d[node[j]].c;
			  }   
			  way[W].node[j] = p;  way[W].total_cost += d[p].c;  W++;
		  }
		  else{ 
			  for(int j=0;j<v_n;j++)  
                  if( d[p].d == v[j] ) break;
                  if( j == v_n){ 
			      v[ v_n] = d[p].d;  node [ n_n] = p;  
				  Next(v,v_n+1,node,n_n+1, d[p].d);
			  }
		  }p++;
	  }
}
bool Myless( const Way &a, const Way & b)
{
	return a.total_cost < b.total_cost;
}
bool  Teg( const Way &a, const Way & b)
{
	for(int i=0; i< a.num_node;i++){
		for(int j=0;j< b.num_node;j++)
            	if( a.node[i] == b.node[j]) return true;
	}
	return false;
}
void work(int start)
{
	if( N== 1){
        printf( "Instance #%d: 0\n", start); return ;
	}
    int *v = new int [64]; 
    int *node = new int[64];

	W = 0; v[0] = 0;
    Next ( v,1,node,0,0);
    
    if( W <2){
        printf( "Instance #%d: Not possible\n", start); return ;
	}

	const _int64 MAX = 999999999999999;
     _int64 rst =MAX;
	for(int i=0; i< W; i++){
		for(int j=i+1; j<W;j++){
             if( !Teg( way[i], way[j]) ){
				 if( way[i].total_cost + way[j].total_cost < rst )
					 rst = way[i].total_cost + way[j].total_cost;
			 }
		}
	}
	if( rst == MAX )
		printf( "Instance #%d: Not possible\n", start);
	else
		printf( "Instance #%d: %I64d\n", start, rst );
	delete [] v; v= NULL;
	delete [] node; node = NULL;
}

bool MyLess( const Node & a, const Node &b) { return a.s < b.s; }
bool over ()
{
	if( N==0 && M ==0) return true;
	return false;
}
int main()
{
  // freopen("C:\\ACMData.txt","r",stdin);
    scanf("%d%d", &N,&M); int i,p,start = 1;
	if( over()) return 1;
	while( true ) {
        i=1;
		while( i <= M){
			scanf("%d %d %I64d",&d[i].s, &d[i].d, &d[i].c); i++;
		}
		sort(d+1,d+M+1, MyLess);
		memset(f,0,sizeof(f));
		for(i=1;i<=M;i++){
            p = d[i].s;
			if( f[p].s == 0 ){
				f[p].s = i; f[p].num = 1;
			}
			else f[p].num ++;
		}
		work(start); start++;
		scanf("%d%d", &N,&M);
		if( over()) return 1;
	}
    return 0;
}