#include <fstream>
#define inf 100000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct nod
{int info,cost;
  nod *urm;
};
nod *prim[50002];
void Addnod(nod *&q, int x,int cost)
{ nod *p;
   p=new nod;
   p->info=x;
   p->cost=cost;
   p->urm=q;
   q=p;
}
int n,m;
/*void Drumuri(int x)
{ int i,nod,min,viz[50002]={0},d[50002],t[50002];
  int gata=0;
  for(i=1;i<=n;i++)
   {d[i]=a[x][i];
    if(d[i]!=inf) t[i]=x;
  viz[x]=1;t[x]=0;
  while(gata==0)
    { min=inf;
      for(i=1;i<=n;i++)
          if(d[i]<min && viz[i]==0)
             {min=d[i];
              nod=i;
             }
     viz[nod]=i;
    if(min!=inf)
     for(i=1;i<=n;i++)
         if(viz[i]==0 && d[nod]+a[nod][i]<d[i])
             {d[i]=d[nod]+a[nod][i];
              t[i]=nod;
             }
   else gata=1;
    }
 for(i=1;i<=n;i++)
  if(i!=x) fout<<d[i]<<" ";
}*/
void Drumuri2(int x)
{int min,z,i,j,viz[50002]={0},d[50002]={0};
  nod *t;
   for(i=1;i<=n;i++)
     if(i!=x) d[i]=inf;
  for(i=1;i<=n;i++)
    {min=inf;
     for(j=1;j<=n;j++)
       if(d[j]<min && viz[j]==0)
           {min=d[j];
            z=j;
           }
      viz[z]=1;
     /*for(p=prim[z];p!=NULL;p=p->urm)
        if(viz[p->info]==0 && d[z]+p->cost<d[p->info])
                d[p->info]=d[z]+p->cost;*/
        t=prim[z];
                while ( t )
        {
            if ( d[ t->info ] > d[z] + t->cost )
                d[ t->info ] = d[z] + t->cost;

            t = t->urm;
        }
     }
for(i=1;i<=n;i++)
  if(i!=x) fout<<d[i]<<" ";
}
int main()
{ int i,j,x,y,z;
  fin>>n>>m;
  /*for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
        a[i][j]=inf;
  for(i=1;i<=m;i++)
     { fin>>x>>y;
       a[x][y];
     }
Drumuri(1);*/
   for(i=1;i<=m;i++)
     {fin>>x>>y>>z;
      Addnod(prim[x],y,z);
     }
  Drumuri2(1);
    return 0;
}