#include <fstream>
#include <vector>
#include <list>
#define NMAX 50005

using namespace std;
long n,m;

struct Nod
{
	long vf,lg;
	Nod(long nvf, long nlg)
	{
		vf=nvf;
		lg=nlg;
	}
};

long lung[NMAX],vizitat[NMAX];

vector< list<Nod> > A;

long minim()
{
	long i,min=LONG_MAX,svi=1;

	for(i=1;i<=n;i++)
		if(vizitat[i]==0 && lung[i]<=min)
		{
			min=lung[i];
			svi=i;
		}

	return svi;
}

int main()
{
	long i,x,y,l,varf;
	fstream fin,fout;

	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);

	fin>>n>>m;
	list<Nod> lista;
	for(i=0;i<=n;i++)
	{
		A.push_back(lista);
		lung[i]=LONG_MAX;
	}
	for(i=0;i<m;i++)
	{
		fin>>x>>y>>l;
		A[x].push_back(Nod(y,l));
		if(x==1)
			lung[y]=l;
	}
	vizitat[1]=1;

	while((varf=minim())!=1)
	{
		vizitat[varf]=1;
		list<Nod>::iterator itr;
		for(itr=A[varf].begin(); itr!= A[varf].end(); itr++)
		{
			if(lung[varf]!=LONG_MAX && lung[(*itr).vf]>(lung[varf]+(*itr).lg))
				lung[(*itr).vf]=lung[varf]+(*itr).lg;
		}
	}

	for(i=2;i<=n;i++)
		if(lung[i]==LONG_MAX)
			fout<<"0 ";
		else
			fout<<lung[i]<<" ";
	fout<<'\n';


	return 0;
}