#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

#define NMAX 50001
#define INF 1<<30

struct NOD {
	int y,cost;
};

NOD heap[NMAX];
vector <NOD> v[NMAX];
int d[NMAX],p[NMAX],nr,n;

inline void up(NOD x)
{
	int k;
	heap[++nr]=x;
	k=nr;
	while(k>=2 && heap[k/2].cost>heap[k].cost) {
		heap[k]=heap[k/2];
		k=k/2;
	}
	heap[k]=x;
}

inline void down()
{
	int k,son;
	k=1;
	heap[k]=heap[nr--];
	son=1;
	while(son) {
		son=0;
		if(2*k<=nr) {
			son=2*k;
			if(2*k+1<=nr) {
				if(heap[2*k+1].cost<heap[son].cost)
					son=2*k+1;
			}
			if(heap[son].cost<=heap[k].cost)
				son=0;
		}
		if(son) {
			swap(heap[k],heap[son]);
			k=son;
		}
	}
}

NOD smax()
{
	NOD x;
	x=heap[1];
	down();
	return x;
}

inline void dijkstra(int nod)
{
	int i;
	NOD x,y;
	nr=1;
	heap[1].y=nod;
	heap[1].cost=0;
	for(i=2;i<=n;i++)
		d[i]=INF;
	while(nr) {
		x=smax();
		if(p[x.y]==0) {
			p[x.y]=1;
			for(vector <NOD> :: iterator it=v[x.y].begin();it!=v[x.y].end();it++)
				if(d[it->y]>d[x.y]+it->cost) {
					d[it->y]=d[x.y]+it->cost;
					y.y=it->y;
					y.cost=d[it->y];
					up(y);
				}
		}
	}
}

int main ()
{
	int m,x,i;
	NOD y;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y.y>>y.cost;
		v[x].push_back(y);
	}
	f.close();
	dijkstra(1);
	for(i=2;i<=n;i++) {
		if(d[i]==INF)
			d[i]=0;
		g<<d[i]<<" ";
	}
	g.close();
	return 0;
}