#include <bits/stdc++.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int Nmax=5e4+5, inf=1e9;
int n,m,x,y,c,dis[Nmax],vis[Nmax];
struct edge {
	int v,c;
	friend bool operator <(edge a,edge b) {
		return a.c>b.c;
	}
};
priority_queue<edge> q;
vector<edge> ad[Nmax];
int main()
{
	in>>n>>m;
	for(int i=1; i<=m; i++) {
		in>>x>>y>>c;
		ad[x].push_back({y,c});
	}
	for(int i=2; i<=n; i++) {
		dis[i]=inf;
	}
	q.push({1,0});
	while(q.size()) {
		edge e=q.top();
		q.pop();
		if(vis[e.v]==0) {
			for(auto it:ad[e.v]) {
				if(vis[it.v]==0 && e.c+it.c<dis[it.v]){
				    dis[it.v]=e.c+it.c;
				    q.push({it.v,dis[it.v]});
				}
			}
		}
		vis[e.v]=1;
	}
	for(int i=2;i<=n;i++)
	{
	    if(dis[i]==inf)
	    out<<0<<' ';
	    else 
	    out<<dis[i]<<' ';
	}
	return 0;
}