#include<fstream>
#include<climits>
#define INF 300000
using namespace std;
ofstream out("dijkstra.out");
int a[20000][20000],n,m,uz[20000],d[20000],T[20000],minim,drum[100];
void citire();
void afis(int *q,int nr);
int dijkstra(int poz);
void drumusor(int x);
int main()
{
	citire();
	dijkstra(1);
	afis(d,n);
	out<<"\n";
	//drumusor(5);
	return 0;
}
void citire()
{
	int x,y,c,i,j;
	ifstream in("dijkstra.in");
	in>>n>>m;
	for(int k=1;k<=m;k++)
	{
		in>>x>>y>>c;
		a[x][y]=c;
	}
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
		if(a[i][j]==0&&i!=j)
			a[i][j]=INF;
}
void afis(int *q,int nr)
{
	for(int i=1;i<=nr;i++)
		if(q[i]!=0)
		out<<q[i]<<" ";
}
int dijkstra(int nod)
{
	int i,j,poz;
	for( i=1;i<=n;i++)
	{
		d[i]=a[nod][i];
		uz[i]=0;
		T[i]=nod;
	}
	uz[nod]=1;
	T[nod]=0;
	for( i=1;i<n;i++)
	{
		minim=INT_MAX;
		for(int k=1;k<=n;k++)
		if(uz[k]==0&&d[k]<minim)
		{
			minim=d[k];
			poz=k;
		}
		uz[poz]=1;
			for(int j=1;j<=n;j++)
				if(uz[j]==0&&d[j]>d[poz]+a[poz][j])
				{
					d[j]=d[poz]+a[poz][j];
					T[j]=poz;
				}
	}
}
void drumusor(int x)
{
	int i,m;
	m=0;
	while(T[x])
	{
		drum[++m]=x;
		x=T[x];
	}
	drum[++m]=x;
	for(i=1;i<=m;i++)
		out<<drum[i]<<" ";
}