#include <fstream>
#define INF 10000
using namespace std;

ofstream fout("dijkstra.out");
int a[100][100],n;
int t[100],//vectorul de tati
	d[100],//vectorul cu distantele minime
	v[100];//vectorul de vizitati

void citire()
{
	ifstream fin("dijkstra.in");
	int i,j,c;
	while(fin>>i>>j>>c)
	{
		a[i][j]=a[j][i]=c;
		if(i>n)
			n=i;
		if(j>n)
			n=j;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]==0)
				a[i][j]=INF;
}

int dijkstra(int start)
{
	int i,j,k;
	for(i=1;i<=n;i++)
		v[i]=0,t[i]=start,d[i]=a[start][i];
	v[start]=1;
	t[start]=0;
	d[0]=INF;//util pentru determinarea minimului
	for(k=1;k<n;k++)
	{
		//determinam varful nevizitat pentru care distanta la start este minima
		//(cea mai mica valoare din d[])
		for(i=1,j=0;i<=n;i++)
			if(v[i]==0)
				if(d[i]<d[j])
					j=i;
		if(!j) // nu am gasit
			return 0;
		v[j]=1;//vizitez varful j
		//actualizez distantele si vectorul de tati
		for(i=1;i<=n;i++)
			if(v[i]==0 && d[i]>d[j]+a[j][i])
				t[i]=j,d[i]=d[j]+a[j][i];
	}
}

void afis(int a[100])
{
	for(int i=2;i<=n;i++)
		fout<<a[i]<<" ";
	fout<<endl;
}

int main()
{
	citire();
	dijkstra(1);
	afis(t);
	return 0;
}