#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int grid[26][26];
char path[100];

bool find (int a, int n, int p)
{
	int i;
	path[p]=a+'A';
	path[p+1]=0;
	bool j=false, f=false, t=false;

	if (a==2)
	{
		for (i=0; i<p; i++)
		{
			j|=(path[i]=='J');
			f|=(path[i]=='F');
			t|=(path[i]=='T');
		}
		if (j&&f&&t) return true;
	}

	for (i=0; i<26; i++)
		if (grid[a][i]<n&&grid[a][i]>0)
			if (find(i,n-grid[a][i],p+1)) return true;

	return false;
}

void main ()
{
	int sets, n, i, j, k, d;
	char a, b;
	char inp[80];

	scanf("%d", &sets);
	for (i=0; i<sets; i++)
	{
		scanf("%d", &n);
		for (j=0; j<26; j++)
			for (k=0; k<26; k++)
				grid[j][k]=0;

		gets(inp);
		for (j=0; j<n; j++)
		{
			gets(inp);
			a=inp[0]-'A';
			b=inp[2]-'A';
			d=atoi(&inp[4]);
			grid[a][b]=d;
		}

		for (j=0; j<10000; j++)
			if (find(0,j, 0))
			{
				printf("Data set %d: The shortest path is %s and has length %d.",
					i+1, path, j-1);
				break;
			}
	}
}