#include<fstream.h>
#include<iostream.h>

int a[251000],h[251000],n,i,L,viz[251000],ind,t,v[251000][3],x,u,poz[251000],s,m,hh[251000];

long ls(long k)
{
 return (k<<1);
 }
long rs(long k)
{
 return ((k<<1)+1);
 }
long f(long k)
{
 return (k>>1);
 }

void ex(long x, long y)
{
 long aux;
 aux=h[x];
 h[x]=h[y];
 h[y]=aux;
 }


void sift(long n, long k)
{
 long son;
 do
  {
   son=0;
   if(ls(k)<=n)
    {
     son=ls(k);
     if(rs(k)<=n&&a[h[rs(k)]]<a[h[son]])son=rs(k);
     if(a[h[son]]>=a[h[k]])son=0;
     }
   if(son)
    {
	 hh[h[son]]=k;
	 hh[h[k]]=son;
     ex(son,k);
     k=son;
     }
    }
   while(son);
 }

void percolate(long k)
{
 long key=h[k];
 while(k>1&&a[key]<a[h[f(k)]])
  {
   h[k]=h[f(k)];
   hh[h[f(k)]]=k;
   k=f(k);
   }
 h[k]=key;
 hh[key]=k;
 }

void bh(long n)
{
 long i;
 for(i=n>>1;i;i--)sift(n,i);
 }

void sterg()
{
	long kk=h[1];
	h[1]=h[L];
	L--;
	sift(L,1);
	hh[kk]=0;
}

void mod(long n, long k)
{
	percolate(hh[k]);
}

/*void cut(long &n, long k)
{
 int kk=k;
 h[v[k]]=h[n];
 n--;
 k=v[k];
 if(k>1&&a[h[k]]<a[h[f(k)]])percolate(k);
 else sift(n,k);
 v[kk]=0;
 }

void insert(long &n, long key)
{
 n++;
 v[++m]=n;
 a[m]=key;
 h[n]=m;
 percolate(n);
 }

*/
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	L=n;
	u=(1<<30);
	for(i=2;i<=n;i++)
		a[i]=u;
	for(i=1;i<=n;i++)
	{
		h[i]=i;
		hh[i]=i;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>v[i][0]>>v[i][2];
		v[i][1]=poz[x];
		poz[x]=i;
	}
	s=0;
	ind=1;
	sterg();
	while(s<n)
	{
		viz[ind]=1;
		s++;
		t=poz[ind];
		while(t)
		{
			if(!viz[v[t][0]])
				if(a[v[t][0]]>a[ind]+v[t][2])
				{
					a[v[t][0]]=a[ind]+v[t][2];
					mod(n,v[t][0]);
				}
					
			t=v[t][1];
		}			
		ind=h[1];
		sterg();
	}
	for(i=2;i<=n;i++)
		if(a[i]==u)
			g<<"0 ";
		else
			g<<a[i]<<' ';
	return 0;
}