#include<fstream>
#include<vector>
#include<queue>
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],viz[nmax];
int n,m;
struct cmp 

{ 

bool operator() (const int &a, const int &b) const

{ 

return d[a]>d[b]; 

} 

}; 
priority_queue <int, vector <int>,cmp> q2;
int main ()
{
	freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
	int i,j,k,a,b,t;
	scanf("%d %d\n", &n, &m);
	for(i=1;i<=m;i++)
		scanf("%d %d %d\n", &a, &b, &t),g[a].pb(b),c[a].pb(t);
	for(i=1;i<=n;i++)
		d[i]=inf;
	q2.push(1);d[1]=0;
	while(!q2.empty())
	{
		a=q2.top();
		viz[a]=0;
		q2.pop();
		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];
				if(viz[g[a][i]]!=1)
				{
				q2.push(g[a][i]);
			
				viz[g[a][i]]=1;
				}
			}
		}
	}
	for(i = 2; i <= n; i++)
        if(d[i]==inf) printf("%d ", 0);
		else printf("%d ", d[i]);
	
	return 0;
}