#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
struct nod {
	int y,cost;
	inline nod ( int _y, int _cost) {
		y=_y;
		cost=_cost;
	}
	inline bool operator < (const nod &c) const {
		return cost>c.cost;
	}
};
priority_queue <nod> c;
vector <nod> v[50001];
int d[50001],l[50001];
bitset <50001> p;
void dijkstra()
{
	int i,x;
	c.push(nod(1,0));
	while(c.empty()==0) {
		x=c.top().y;
		c.pop();
		if(p[x]==0) {
			p[x]=1;
			for(i=0;i<=l[x];i++) 
				if(d[v[x][i].y]>(d[x]+v[x][i].cost)) {
					d[v[x][i].y]=d[x]+v[x][i].cost;
					c.push(nod(v[x][i].y,d[v[x][i].y]));
				}
		}
	}
}
int main ()
{
	int i,n,m,x,y,cost;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		v[x].push_back(nod(y,cost));
	}
	f.close();
	for(i=1;i<=n;i++) {
		l[i]=v[i].size()-1;
		d[i]=2147000000;
	}
	d[1]=0;
	dijkstra();
	for(i=2;i<=n;i++) {
		if(d[i]==2147000000)
			d[i]=0;
		g<<d[i]<<" ";
	}
	g.close();
	return 0;
}