#include <assert.h>
#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define OO 1000000000

FILE *input;
int n,r,n1,n2,i1,i2,s=0;
char city[256][32];
double a[256][256];

int readcase ()
{
  char c1[32],c2[32];
  double d;
  int i;
  s++;
  fscanf (input, " %d %d ", &n, &r);
  if (n==0 && r==0) return 0;
  n1=n2=0;
  for (i1=0 ; i1<256 ; i1++) for (i2=0 ; i2<256 ; i2++) a[i1][i2]=0.0;
  for (i1=0 ; i1<256 ; i1++) a[i1][i1]=OO;
  for (i=0 ; i<=r ; i++)
    {
      fscanf (input, " %s %s ", c1, c2);
      for (i1=0 ; i1<n1 ; i1++) if (strcmp (c1,city[i1])==0) break;
      if (i1==n1) strcpy (city[n1++],c1);
      for (i2=0 ; i2<n1 ; i2++) if (strcmp (c2,city[i2])==0) break;
      if (i2==n1) strcpy (city[n1++],c2);
      if (i==r) break;
      fscanf (input, " %lf ", &d);
      a[i1][i2]=a[i2][i1]=d;
    }
  return 1;
}

void solvecase ()
{
  int i,j,k;
  for (k=0 ; k<n1 ; k++)
    for (i=0 ; i<n1 ; i++)
      for (j=0 ; j<n1 ; j++)
	a[i][j] = MAX (a[i][j],MIN(a[i][k],a[k][j]));
  printf ("Scenario #%d\n",s);
  printf ("%.0f tons\n\n", a[i1][i2]);
}

int main ()
{
  input = fopen ("heavy.in","r");
  assert (input != NULL);
  while (readcase ()) solvecase ();
  fclose (input);
  return 0;
}