#include <stdio.h>
#include <vector>
#include <set>

using namespace std;

FILE *f,*s;

struct nod
{
	long int x;
	long int y;
};

nod nod1;

vector <nod> v1[250000];

set <pair <long int, long int> > h1;

vector <nod> ::iterator it;

pair <long int, long int> nod2;

long int i,m,n;

long int v2[250005];

int main()
{
	f=fopen("dijkstra.in","r");
	s=fopen("dijkstra.out","w");
	
	fscanf(f,"%ld %ld",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		int a,b,c;
		
		fscanf(f,"%ld %ld %ld",&a,&b,&c);
		
		nod1.x=b;
		nod1.y=c;
		
		v1[a].push_back(nod1);
	}
	
	for(i=1;i<=n;i++) v2[i]=5000000;
	
	v2[1]=0;
	
	h1.insert(make_pair(0,1));
	
	while(h1.size())
	{
		nod2=*h1.begin();
		h1.erase(h1.begin());
		
		for(it=v1[nod2.second].begin();it!=v1[nod2.second].end();it++)
		{	
            if(v2[(*it).x]>nod2.first+(*it).y)
            {
                h1.erase(make_pair(v2[(*it).x],(*it).x));
				
				v2[(*it).x]=nod2.first+(*it).y;

                h1.insert(make_pair(v2[(*it).x],(*it).x));
            }
		}
	}
	
	for(i=2;i<=n;i++)
	{
		if(v2[i]!=5000000)
			fprintf(s,"%ld ",v2[i]);
		else
			fprintf(s,"0 ");
	}
	
	fclose(s);
	
	return 0;
}