#include<iostream>
#include<fstream>
#define infin 10000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int C[5000][5000],d[5000],tata[5000],viz[5000],n,m;
void read ()
{ int x,y,cost;
     in>>n>>m;
     for(int i=1;i<=n; ++i)
          for(int j=1; j<=n; ++j)
            if(i==j)
              C[i][j]=0;
                else
             C[i][j]=infin;
 for(int i=1; i<=m; i++)
 {  in>>x>>y>>cost;
    C[x][y]=cost;
 }
}

void dijkstra (int nod)
{   int ok,min,k;
     for(int i=1; i<=n; ++i)
     {  d[i]=C[nod][i];
        viz[i]=0;
        tata[i]=nod;

     }

     ok=1;
     viz[nod]=1;
     tata[nod]=0;
     while(ok)
     {
          min=infin;
          for(int i=1; i<=n; i++)
              if(min>d[i] && !viz[i])
              {
                  min=d[i];
                  k=i;
              }

              if(min!=infin)
              {
                  viz[k]=1;
                  for(int i=1; i<=n; i++)
                      if(viz[i]==0 && d[i]>d[k]+C[k][i])
                   {    d[i]=d[k]+C[k][i];
                       tata[k]=i;
                   }
              }
              else
                ok=0;
     }

}
int main ()
{
      read();
      dijkstra(1);
      for(int i=2; i<=n; i++)
            cout<<d[i]<<" " ;

      in.close();
      out.close();
      return 0;

}