#include<fstream>
#include<iostream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int A[1400][1400],n,m,s[1400],d[1400],t[1400],infinit=1000000000;

void citire()
{	
	in>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j)
				A[i][j]=infinit;
	int x,y,c;

	for(int i=1;i<=m;i++)
	{
		in>>x>>y>>c;
		A[x][y]=c;
	}
}

void dijkstra(int r)
{
	s[r]=1;
	for(int i=1;i<=n;i++)
	{
		d[i]=A[r][i];
		if(d[i]<infinit)
			t[i]=r;
	}
	for(int j=1;j<=n-1;j++)
	{
		int min=infinit,nodsel;
		for(int i=1;i<=n;i++)
			if(s[i]==0 && d[i]<min)
			{
				min=d[i];
				nodsel=i;
			}
		s[nodsel]=1;
		for(int i=1;i<=n;i++)
			if(s[i]==0)
			{
				int sc=d[nodsel]+A[nodsel][i];
				if(sc<d[i])
				{
					d[i]=sc;
					t[i]=nodsel;
				}
			}
			
	}
}

int main()
{
	citire();
	int r=1;
	//cin>>r;
	dijkstra(r);
	for(int i=2;i<=n;i++)
		if(d[i]<infinit)
			out<<d[i]<<" ";
		else
			out<<0<<" ";
	return 0;
}