#include<bits/stdc++.h>
#define pb push_back
#define inf 100000000
using namespace std;

int main(){
    int cs = 1;
    while(1){
        int n, m; cin >> n >> m;
        if(n == 0) break;
        vector<string> v(n);
        for(auto &x : v) cin >> x;
        int adj[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) adj[i][j] = 0;
                else adj[i][j] = inf;
            }
        }
        for(int i = 0; i < m; i++){
            int x, y, w; cin >> x >> y >> w;
            adj[x][y] = w;
            adj[y][x] = w;
        }
        for(int k = 1; k <= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    adj[i][j] = min(adj[i][j], adj[i][k]+adj[k][j]);
                }
            }
        }
        int kodu = 1e9, house;
        for(int i = 1; i <= n; i++){
            int val = 0;
            for(int j = 1; j <= n; j++){
                val += adj[i][j];
            }
            if(val < kodu) house = i, kodu = val;
        }
        cout << "Case #" << cs << " : " << v[house-1] << endl;
    }
}