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

#define NMAX 50001
#define INF 1<<30

struct muchie {
	int y,cost;
};

vector <muchie> v[NMAX];
int d[NMAX],viz[NMAX],nr;
muchie heap[2*NMAX+1];

void up()
{
	int k;
	k=nr;
	while(k>1 && heap[k].cost<heap[k/2].cost) {
		swap(heap[k],heap[k/2]);
		k=k/2;
	}
}

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

int SMAX()
{
	int nod;
	nod=heap[1].y;
	down();
	return nod;
}

void dijkstra()
{
	int nod;
	nr=1;
	heap[1].y=1;
	heap[1].cost=0;
	while(nr) {
		nod=SMAX();
		if(viz[nod]==0) {
			viz[nod]=1;
			for(vector <muchie> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
				if(d[it->y]>d[nod]+it->cost) {
					d[it->y]=d[nod]+it->cost;
					heap[++nr].y=it->y;
					heap[nr].cost=d[it->y];
					up();
				}
		}
	}
}

int main ()
{
	int i,m,x,n;
	muchie 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();
	for(i=2;i<=n;i++)
		d[i]=INF;
	dijkstra();
	for(i=2;i<=n;i++) {
		if(d[i]==INF)
			d[i]=0;
		g<<d[i]<<" ";
	}
	g.close();
	return 0;
}