#include <fstream.h>
#define dim 50005
#define inf 5000005

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


struct list{long nod; int cost; list *urm;};

long n,m,r;
long h[dim],d[dim],poz[dim];
list *l[dim];



void add(long x,long y, int c)
{list *p=new list;
 p->nod=y;
 p->cost=c;

 p->urm=l[x];
 l[x]=p;

 if (x==r) d[y]=c;
}


void heap_up(long k)
{long aux;
 while(k>1 && d[h[k/2]]>d[h[k]])
  {aux=h[k/2];
   h[k/2]=h[k];
   h[k]=aux;

   poz[h[k/2]]=k/2;
   poz[h[k]]=k;

   k=k/2;
   }
}




void heap_down(long k)
{long aux,fiu=0;

 do {fiu=0;

     if (2*k<=m)
       {fiu=2*k;
	if (d[h[fiu+1]]<d[h[fiu]]) fiu++;
	}

     if (d[h[fiu]]>=d[k]) fiu=0;
      else
       {aux=h[fiu];
	h[fiu]=h[k];
	h[k]=aux;

	poz[h[fiu]]=fiu;
	poz[h[k]]=k;

	k=fiu;
       }
  }while (fiu>0);
}



void extrage(long k)
{
 poz[h[m]]=poz[h[k]];
 poz[h[k]]=0;

 h[k]=h[m];
 m--;

 if (k>1 && d[h[k/2]]>d[h[k]])
   heap_up(k);
   else
    heap_down(k);


}




int main()
{long i,nod,x,y;
 int c;
 list *p;

 fin>>n>>m;

 r=1;

 for (i=1;i<=n;i++) d[i]=inf;
 d[r]=0;

 for (i=1;i<=m;i++)
  {fin>>x>>y>>c;
   add(x,y,c);
   }



 for (i=1;i<r;i++) poz[i]=h[i]=i;
 for (i=r+1;i<=n;i++) poz[i]=i;

 for (i=r;i<=n-1;i++) h[i]=poz[i+1];



 m=n-1;
 for (i=m;i>0;i--) heap_up(i);



 while (m>0)  //DIJKSTRA
 {nod=h[1];
  extrage(1);


  for (p=l[nod];p;p=p->urm)
    if (d[p->nod]>d[nod]+p->cost)
	{d[p->nod]=d[nod]+p->cost;
	 heap_up(poz[p->nod]);
	 }
  }



for (i=1;i<=n;i++)
 if (i!=r) fout<<d[i]<<" ";


fout.close();
return 0;
}