#include <cstdio>
#define inf (1<<29)
#define N 50001
using namespace std;
int n,viz[N],d[N];
struct Nod{
          int nod,cost;
          Nod *leg;
          }*l[N];
void read()
{
int i,x,y,m,c;
Nod *p;
freopen("dijkstra.in","r",stdin);
scanf("%d%d",&n,&m);
while (m--)
    {
    scanf("%d%d%d",&x,&y,&c);
    p=new Nod;p->nod=y;p->cost=c;p->leg=l[x];l[x]=p;
    }
}
void dijkstra()
{
int pas,i,j,vfmin,min,gata=0,c;
Nod *p;
freopen("dijkstra.out","w",stdout);
for (i=1;i<=n;i++)
   d[i]=inf;
d[1]=0;
for (pas=1;pas<n && !gata;pas++)
   {
   min=inf;
   for (i=1;i<=n;i++)
   if (!viz[i] && d[i]<min) {
                             vfmin=i;
                             min=d[i];
                             }
    if (min==inf) gata=1;
    else {
       viz[vfmin]=1;
       for (p=l[vfmin];p!=NULL;p=p->leg)
             {
             j=p->nod;c=p->cost;
             if (!viz[j] && d[j]>c+d[vfmin])
                 d[j]=c+d[vfmin];
             }
        }
   }
for (i=2;i<=n;i++)
printf("%d ",d[i]);
}
int main()
{
read();
dijkstra();
}