Q544: Heavy Cargo

// Accepted !!

// Floyd_Warshall problem

#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX 200

char city[MAX][31];
int matrix[MAX][MAX], _index;
int check(char tmp[]);
void Floyd_Warshall(int n);

using namespace std;

int main()
{
    int n, r, a, b, w, t = 1;
    char tmp[31];

    while(cin >> n >> r)
    {
        if(n == 0 && r == 0)
            break;

        getchar();
        _index = 0;

        for(int i = 0; i < r; i++)
        {
             cin >> tmp;
             a = check(tmp);
             cin >> tmp;
             b = check(tmp);
             cin >> w;
             matrix[a][b] = matrix[b][a] = w;
        }
        Floyd_Warshall(_index);
        cin >> tmp;
        a = check(tmp);
        cin >> tmp;
        b = check(tmp);

        cout << "Scenario #" << t++ << endl;
        cout << matrix[a][b] << " tons" << endl << endl;
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

int check(char tmp[])
{
    for(int i = 1; i <= _index; i++)
    {
        if(strcmp(city[i],tmp) == 0)

            return i;
    }
    _index++;
    strcpy(city[_index],tmp);
    return _index;
}

void Floyd_Warshall(int n)
{
     for(int k = 1; k <= n; k++)
         for(int i = 1; i <= n; i++)
             for(int j = 1; j <= n; j++)
                 matrix[i][j] = max(matrix[i][j],min(matrix[i][k],matrix[k][j]));
}