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

void dijkstra(int x)
{
     int ok,min,k,d[n+5],viz[n+5],C[n+5][n+5],q,y,cost;;

     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++)
        { f>>q>>y>>cost;
          C[q][y]=cost;
        }

     for(int i=1; i<=n;i++)
           {
             viz[i]=0;
             d[i]=C[x][i];
           }
           viz[x]=1;
           ok=1;
     for(int j=1;j<=n-1;j++)
        {  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];
                         }



        }

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



}

 int main ()
 {

     f>>n>>m;

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