#include<fstream>
#include<vector>
#include <cstdio>
#include <cstring>
using namespace std;
#define nmax 50100
#define pb push_back
#define inf 1000000000
vector<int> g[nmax],c[nmax];
int d[nmax],q[1<<20];
int n,sf,inc,m;
int main ()
{
	ifstream f("dijkstra.in");
    ofstream fout("dijkstra.out")
	int i,j,k,a,b,t;
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>a>>b>>t,g[a].pb(b),c[a].pb(t);
	for(i=1;i<=n;i++)
		d[i]=inf;
	inc=sf=0;
	q[0]=1;d[1]=0;
	while(inc<=sf)
	{
		a=q[inc++];
		for(i = 0; i < g[a].size(); i++)
        if( d[ g[a][i] ] > d[a] + c[a][i] )
          d[ g[a][i] ] = d[a] + c[a][i], q[++sf] = g[a][i];
	}
	for(i = 2; i <= n; i++)
        if(d[i]==inf) fout<<0<<' ';
		else fout<<d[i]<<' ';
	f.close();
	return 0;
}