11015

#include <iostream>
#include <string.h>
#include <vector>
#include <map>

#define ll long long
#define INF 1000000000

using namespace std;

int graph[25][25];
int N,M,MiN;
int sum[25];
map<int,string> m;

int main()
{
	int t,kase=1;
	int a,b,c,res;
	string s;
	//cin>>t;

	while(cin>>N)
	{
		cin>>M;
		if(N==0 )
		break;
		//mp.clear();
		m.clear();
		int x=1;

		for(int i=1;i<25;i++)
		{
			sum[i]=0;
			for(int j=1;j<25;j++)
			{
				graph[i][j]=INF;
				if(i==j)
				graph[i][j]=0;
			}

		}
		for(int i=0;i<N;i++)
		{
			cin>>s;
			m[i+1]=s;
		}

		for(int i=0;i<M;i++)
		{
			cin>>a>>b>>c;
			graph[a][b]=c;
			graph[b][a]=c;
		}

		MiN = INF;
		for(int k=1;k<=N;k++)
		{
			for(int i=1;i<=N;i++)
			{
				for(int j=1;j<=N;j++)
				{
					if(graph[i][j]>(graph[i][k]+graph[k][j]))
						graph[i][j] = (graph[i][k]+graph[k][j]);
				}
			}
		}

		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			sum[i]+=graph[i][j];

			if(sum[i]<MiN)
			{
				MiN = sum[i];
				res = i;
			}
		}
		cout<<"Case #"<<kase++<<" : "<<m[res]<<"\n";
	}

	return 0;
}