#include<bits/stdc++.h>
using namespace std;
const int N=50020, INF=1e9;
vector <pair<int,int> > lda[N];
set <pair<int,int> > q;
int d[N];
int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	int n, m, x, y, z;
	f>>n>>m;
	while(m--){
		f>>x>>y>>z;
		lda[x].push_back({y, z});
	}
	for(int i=2;i<=n;i++)d[i]=INF;
	q.insert({0,1});
	while(!q.empty()){
		int nod=q.begin()->second;
		m=lda[nod].size();
		q.erase(q.begin());
		for(int i=0;i<m;i++)if(d[nod]+lda[nod][i].second<d[lda[nod][i].first]){
			int x=lda[nod][i].first, y=lda[nod][i].second;
			if(d[lda[nod][i].first]!=INF){
				q.erase(q.find({d[x], x}));
			}
			d[x]=d[nod]+y;
			q.insert({d[x], x});
		}
	}
	for(int i=2;i<=n;i++)if(d[i]==INF)g<<"0 "; else g<<d[i]<<' ';
}