// graf1.cpp : Defines the entry point for the console application.
//

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define word unsigned int
#include <iostream>
#include <fstream>
using namespace std;
int i, j, n, p, xn, xk;
int flag[11];
unsigned int c[11][11], l[11];
char s[80], path[80][11];

int min(int n)
{

	int i, result;

	for (i = 0; i < n; i++)

		if (!(flag[i])) result = i;

	for (i = 0; i < n; i++)

		if ((l[result] > l[i]) && (!flag[i])) result = i;

	return result;

}

unsigned int minim(unsigned int x, unsigned int y)
{
	if (x < y)
		return x;
	return y;
}
int main()
{
	ifstream in("input.txt");
	if (!in)
	{
		cout << "ne mogu otkrit' fail\n";
		return 1;
	}

	in >> n;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) c[i][j] = 0;

	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			in >> c[i][j];

	for (i = 0; i < n; i++) cout << "x" << i + 1;
	cout << endl << endl;
	for (i = 0; i < n; i++)
	{
		printf("x%d", i + 1);
		for (j = 0; j < n; j++)
		{
			printf("%6d", c[i][j]);
			c[j][i] = c[i][j];
		}
		printf("nn\n");
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (c[i][j] == 0) c[i][j] = 65535;

	in >> xn;
	in >> xk;

	in.close();

	xk--;
	xn--;
	if (xn == xk)
	{
		cout << "nachalnaya i konechnaya tichki sovpadayt:" << endl;
		getchar();
		getchar();
		return 0;
	}
	for (i = 0; i < n; i++)
	{
		flag[i] = 0;
		l[i] = 65535;
	}
	l[xn] = 0;
	flag[xn] = 1;
	p = xn;
	_itoa_s(xn + 1, s, 10);
	for (i = 0; i < n; i++)
	{
		strcpy_s(path[i], "x");
		strcat_s(path[i], s);
	}
	do
	{
		for (i = 0; i < n; i++)
			if ((c[p][i] != 65535) && (!flag[i]) && (i != p))
			{
				if (l[i]>l[p] + c[p][i])
				{
					_itoa_s(i + 1, s, 10);
					strcpy_s(path[i + 1], path[p + 1]);
					strcat_s(path[i + 1], "-x");
					strcat_s(path[i + 1], s);
				}
				l[i] = minim(l[i], l[p] + c[p][i]);
			}
		p = min(n);
		flag[p] = 1;
	} while (p != xk);
	if (l[p] != 65535)
	{
		cout << "put:" << path[p + 1] << endl;
		cout << "dlina puti:" << l[p] << endl;
	}
	else
		cout << "takogo puti ne syshestvuet!" << endl;
	getchar();
	getchar();

	return 0;
}