#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

string c[20], s1, s2;
int z, i, a, n, cit, mini;
int p[20][20];

void t (int cur, int sum){
	cout << cur << " ";
	if (c[cur]=="SEA" && sum<mini){
		mini=sum;
		cout << endl;
		return;
	}
	
	for (i=0; i<cit; ++i){
		if (p[cur][i]>=0){
			t(i,sum+p[cur][i]);
		}
	}
	
	return;
}

int main (){
	freopen ("data5.txt", "r", stdin);
	freopen ("out5.txt", "w", stdout);
	int z, start, x, y, b;
	
	for (z=0; z<5; ++z){
		cin >> n;
		cit=0;
		for (i=0; i<20; ++i){
			for (a=0; a<20; ++a){
				p[i][a]=-1;
			}
		}
		for (b=0; b<n; ++b){
			mini=100000000LL;
			cin >> s1 >> s2 >> a;
			x=21;
			for (i=0; i<cit; ++i){
				if (s1==c[i]){
					x=i;
					break;
				}
			}
			if (x==21){
				x=cit;
				c[cit]=s1;
				++cit;
			}
			y=21;
			for (i=0; i<cit; ++i){
				if (s2==c[i]){
					y=i;
					break;
				}
			}
			if (y==21){
				y=cit;
				c[cit]=s2;
				++cit;
			}
			p[x][y]=a;
		}
		cout << cit << endl;
		for (i=0; i<cit; ++i){
			for (a=0; a<cit; ++a){
				cout << p[i][a] << " ";
			}
			cout << endl;
		}
		for (i=0; i<cit; ++i){
			if (c[i]=="YYZ"){
				start=i;
				break;
			}
		}
		t(start,0);
		cout << mini << endl;
	}
	
	return 0;
}