#include <fstream>
#include <list>
#include <vector>

#define NMAX 50005

using namespace std;

long n,m,nev,vizitat[NMAX],varf;
long lung[NMAX];

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

vector<list<Nod*>*> lst;



long minim()
{
	long min=lung[1],i=2,svi=1;
	while(i<=n)
	{
		if(lung[i]<min && vizitat[i]==0)
		{
			min=lung[i];
			svi=i;
		}
		i++;
	}
	return svi;
}

int main()
{
	long i,x,y;
	long l;
	fstream fin,fout;
	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);


	fin>>n>>m;
	for(i=0;i<n+1;i++)
	{
		lst.push_back(new list<Nod*>);
		lung[i]=LONG_MAX;
	}
	for(i=0;i<m;i++)
	{
		fin>>x>>y>>l;
		lst[i]->push_back(new 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=lst[varf]->begin(); itr!= lst[varf]->end(); itr++)
		{
			if(lung[(*itr)->vf]>lung[varf]+lung[(*itr)->lg])
				lung[(*itr)->vf]=lung[varf]+lung[(*itr)->lg];
		}
	}

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

	fout.close();
	fin.close();
	return 0;
}