#include<stdio.h>
#include<vector>
#include<queue>
#include<utility>

#define x first
#define y second
#define Nmax 50001


using namespace std;

FILE *in,*out;

int n,m;
int nod1,nod2,d;
int dist[Nmax];

vector<pair<int,int> > graf[Nmax];
priority_queue<pair<int,int> , vector<pair<int,int> > , greater<pair<int,int> > > q;

int main(void)
{ 
	in=fopen("dijkstra.in","rt");
	out=fopen("dijkstra.out","wt");
	fscanf(in,"%d%d",&n,&m);
	dist[1]=0;
	for(int i=2;i<=n;++i)
		dist[i]=(1<<30)-1;
	for(int i=1;i<=m;++i)
	{
		fscanf(in,"%d%d%d",&nod1,&nod2,&d);
		graf[nod1].push_back(make_pair(d,nod2));
	}	
	
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		pair<int,int> curent=q.top();
		q.pop();
		vector<pair<int,int> > :: iterator it,end=graf[curent.y].end();
		for(it=graf[curent.y].begin() ; it!=end ; ++it)
		{
			if(curent.x+ it->x < dist[it->y])
			{
				dist[it->y]=curent.x+it->x;
				q.push(make_pair(curent.x+it->x,it->y));
			}	
			
		}			
	}	
	for(int i=2;i<=n;i++)
		if(dist[i]==(1<<30)-1)
			fprintf(out,"0 ");
		else
			fprintf(out,"%d ",dist[i]);
	fclose(in);
	fclose(out);
	return 0;
}