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

const int SIZE = 1001;
const int INFINITE = 0x7f7f7f7f;
int graph[SIZE][SIZE], n, m;
bool visited[SIZE];

class Node
{
public:
	int v, w;
	Node() {}
	Node( int a, int b ) { v = a, w = b; }
public:
	bool operator < ( const Node node ) const
	{
		return w > node.w;
	}
};

priority_queue <Node> q;

int min( int a, int b )
{
	return a < b ? a : b;
}

void dij()
{
	int ans = -1;

	memset( visited, false, sizeof( visited ) );
	q.push( Node( 1, INFINITE ) );

	while( !q.empty() )
	{
		Node tmp = q.top();
		q.pop();

		if( tmp.v == n )
		{
			ans = ans > tmp.w ? ans : tmp.w;
			continue;
		}

		if( visited[tmp.v] )
			continue;

		visited[tmp.v] = true;
		for( int i = 1; i <= n; i++ )
			if( !visited[i] && graph[tmp.v][i] < INFINITE )
				q.push( Node( i, min( tmp.w, graph[tmp.v][i] ) ) );
	}

	printf( "%d\n\n", ans );
}

int main ()
{
	int s, i, j, k;
        //freopen ( "1797.txt", "r", stdin );
	for ( k = 1, scanf ( "%d", &s ); k <= s; k++ )
	{
		printf ( "Scenario #%d:\n", k );
		scanf ( "%d%d", &n, &m );

		for ( i = 1; i <= n; i++ )
		{
			for ( j = 1; j <= n; j++ )
				graph[i][j] = INFINITE;
		}

		for ( j = 0; j < m; j++ )
		{
			int from, to, weight;
			scanf ( "%d%d%d", &from, &to, &weight );
			graph[from][to] = graph[to][from] = weight;
		}

		if ( n == 1 )
		{
			printf ( "0\n\n" );
			continue;
		}

		dij();
	}

	return 0;
}