Q11015: 05-2 Rendezvous

// Accepted !!

// Floyd_Warshall problem

#include <iostream>
#include <cstdlib>
#include <algorithm>
#define MAX 23

using namespace std;

int matrix[MAX][MAX];
void Floyed_Warshall(int n);

int main()
{
    int N, M, a, b, cost, index = 1;
    char name[MAX][11];

    while(cin >> N >> M)
    {
        if(N == 0 && M == 0)
            break;

        for(int i = 1; i <= N; i++)
        {
            cin >> name[i];
            for(int j = i+1; j <= N; j++)
                matrix[j][i] = matrix[i][j] = 99999;
            matrix[i][i] = 0;
        }

        for(int i = 1; i <= M; i++)
        {
            cin >> a >> b >> cost;
            matrix[a][b] = cost;
            matrix[b][a] = cost;
        }

        Floyed_Warshall(N);
        int tmp, answer, min = 99999;

        for(int i = 1; i <= N; i++)
        {
            tmp = 0;
            for(int j = 1; j <= N; j++)
                tmp += matrix[i][j];
            if(tmp < min)
            {
                min = tmp;
                answer = i;
            }
        }
        cout << "Case #" << index++ << " : " << name[answer] << endl;
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

void Floyed_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] = min(matrix[i][j],matrix[i][k] + matrix[k][j]);
}