#include<iostream>
#include<fstream>
#define infin  10000000
using namespace std;
ifstream f("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,C[20000][20000];

void dijkstra(int x)
{
     int ok,min,k,d[50005],viz[50005];

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

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


                }
              else
              ok=0;
        }


              for(int i=2;i<=n;i++)
                out<<d[i]<<" ";


}




 int main ()
 {
      int x,y,cost;
     f>>n>>m;

      for(int i=1; i<n; i++)
         for(int j=i;j<=n;j++)
           if(i==j)
             C[i][j]=0;
             else
            C[i][j]=infin;



      for(int i=1; i<=m;i++)
        { f>>x>>y>>cost;
          C[x][y]=cost;
        }

   dijkstra(1);
   f.close();
   out.close();
   return 0;
}