# include <fstream>
# include <vector>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

# define nmax 50001
# define inf 5000000

vector <int> v[nmax],d[nmax];
int n,m,st[nmax],l,km[nmax];bool viz[nmax];

void citire()
{
	f>>n>>m;
	int i,j,dist;
	for(i=1;i<=m;i++)
	{
		f>>i>>j>>dist;
		v[i].push_back(j);d[i].push_back(dist);
	}
}

int main()
{
	citire();
	st[1]=viz[1]=1;
	int pi=1,pj=1,i,j,vec;
	memset(km,inf,sizeof(km));
	
	while(pi<=pj)
	{
		i=st[pi];km[1]=0;
		l=v[i].size();
		for(j=0;j<l;j++)
		{
			vec=v[i][j];
			
			if( !viz[vec] && km[vec]>km[i]+d[i][j])
			{
				km[vec]=km[i]+d[i][j];
				pj++;st[pj]=vec;
			}
		}
		viz[i]=1;
		pi++;
	}
	for(i=2;i<=n;i++)
		if(km[i]==inf) g<<0<<" ";
		else g<<km[i]<<" ";
}