#include <fstream>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define MAX 1001
#define dim 21000

using namespace std;

int a[dim][dim],d[dim],p[dim],s[dim],n,m;

void citire()
{
	int i,j,x,y;
	ifstream in(infile);
	in>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			if (i==j)
				a[i][j]=0;
			else
				a[i][j]=MAX;
	for (i=1;i<=m;i++)
	{
		in>>x>>y;
		in>>a[x][y];
	}
	in.close();
}


void generare_drum(int x)
{
	int min,y,i,j;
	s[x]=1;
	for (i=1;i<=n;i++)
		d[i]=a[x][i];
	for (i=1;i<n;i++)
	{
		for (j=1,min=MAX;j<=n;j++)
			if(s[j]==0 &&d[j]<min)
			{
				min=d[j];
				y=j;
			}
		s[y]=1;
		for (j=1;j<=n;j++)
			if (s[j]!=1 && d[j]>d[y]+a[y][j])
				d[j]=d[y]+a[y][j];
	}
}
int main (void)
{
	citire();
	ofstream out(outfile);
	generare_drum(1);
	for (int i=2;i<=n;i++)
		out<<d[i]<<" ";
	out.close();
	return 0;
}