#include<fstream>
#define MAXX 999999999
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod{int inf,c; nod *urm;};
nod *l[50002];

int d[50002],x[50002],poz[50002],n,m,nh,r;



void add(int p1,int p2,int cost)
{
	nod *q;

	q=new nod;
	q->inf=p2;
	q->c=cost;

	q->urm=l[p1];
	l[p1]=q;
}




void citire()
{
	int p1,p2,cost,i;

	fin>>n>>m;
	r=1;

	for(i=1;i<=m;i++)
	{
		fin>>p1>>p2>>cost;
		add(p1,p2,cost);
	}

	fin.close();
}




void swap(int i,int j)
{
	int aux;

	aux=x[i];
	x[i]=x[j];
	x[j]=aux;

	poz[x[i]]=i;
	poz[x[j]]=j;
}





void HeapUP(int k)
{
	int i;

	if(k<=1)
		return ;

	i=k/2;

	if(d[x[k]]<d[x[i]])
	{
		swap(i,k);
		HeapUP(i);
	}
}




void BuildH(int k)
{
	int i;

	for(i=1;i<=n;i++)
		HeapUP(i);
}




void HeapDW(int r,int k)
{
	int st,dr,i;

	if(2*r<=k)
	{
		st=x[2*r];

		if(2*r+1<=k)
			dr=x[2*r+1];
		else
			dr=-2;

	if(d[st]<d[dr] || dr==-2)
		i=2*r;
	else
		i=2*r+1;


	if(d[x[r]]>d[x[i]])
	 {
		swap(r,i);
		HeapDW(i,k);
	 }
	else
		return;

	}
}




int scoate_heap()
{
	swap(1,nh);
	poz[x[nh]]=0;
	nh--;
	HeapDW(1,nh);

	return x[nh+1];
}




void Dijkstra()
{
	int i,k;
	nod *p;

	for(i=1;i<=n;i++)
	{
		d[i]=MAXX;
		x[i]=i;
		poz[i]=i;
	}


	d[r]=0; nh=n;

    BuildH(n);


	while(nh>0)
	{
		k=scoate_heap();

		p=l[k];

		while(p)
		{
			if(d[p->inf] > d[k]+p->c && poz[p->inf])
			{
				d[p->inf]=d[k]+p->c;

				HeapUP(poz[p->inf]);
			}

			p=p->urm;
		}
	}
}





void afis()
{
	int i;

	for(i=1;i<=n;i++)
		if(i!=r)
		{
		 if(d[i]<MAXX)
			fout<<d[i]<<" ";
		else
			fout<<0<<" ";
		}

	fout.close();
}




int main()
{
	citire();
	Dijkstra();
	afis();

	return 0;
}