#include<iostream>
#include<fstream>
#include<vector>
#include<deque>
#define inf 0xfffffff
using namespace std;
struct nod{
	int y,c;
};
vector <nod> v[50001];
deque <int> coada;
int n,m,d[50001];
void citire(){
	ifstream f("dijkstra.in");
	f>>n>>m;
	int x;
	nod t;
	for(int i=1;i<=m;i++){
		f>>x>>t.y>>t.c;
		v[x].push_back(t);
	}
	f.close();
}
void dijkstra(){
	for(int i=2;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	coada.push_back(1);
	while(!coada.empty()){
		int x=coada.front();
		if(d[x]!=inf)
			for(int i=0;i<v[x].size();i++){
				int y=v[x][i].y;
				int c=v[x][i].c;
				if(d[y]>d[x]+c){
					d[y]=d[x]+c;
					coada.push_back(y);
				}
			}
			coada.pop_front();
	}
}
int main(){
	citire();
	ofstream g("dijkstra.out");
	dijkstra();
	for(int i=2;i<=n;i++)
		if(d[i]!=inf)
			g<<d[i]<<" ";
		else
			cout<<"0"<<" ";
	g.close();
	return 0;
}