#include<fstream>
#include<iostream>

using namespace std;

#define infinit 100000
#define max 5000
int a[max][max], n,m, start, d[max], s[max], prec[max];

void citire()
{
     int i, j, x, y, cost;
     ifstream f("dijkstra.in");
        f>>n>>m;
        
     for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
          a[i][j]=infinit;
          
     for(i=1;i<=m;i++)
      {
        f>>x>>y>>cost;
        a[x][y]=cost;
      }
      
     f.close();
}

void initializare()
{
  int i;
  s[start]=1;
  
  for(i=1;i<=n;i++)
    if(a[start][i]!=infinit)
       {
         d[i]=a[start][i];
         prec[i]=start;
       }
     else
       d[i]=infinit;
     
}

void dijkstra()
{
     int gasit, min, k=start, i;
     
     do{
         gasit=0;
         min=infinit;
         for(i=1;i<=n;i++)
           if(s[i]==0&&d[i]<min)
              {
                min=d[i];
                k=i;
                gasit=1;
              }
           s[k]=1;
           
         for(i=1;i<=n;i++)
            if(d[i]>d[k]+a[k][i])
              {
                prec[i]=k;
                d[i]=d[k]+a[k][i];
              }
         }while(gasit);
}

void afisare()
{ 
     int i;
     ofstream g("dijkstra.out");
     for(i=2;i<=n;i++)
        g<<d[i]<<" ";
     
}

int main()
{
    citire();
    start=1;
    initializare();
    dijkstra();
    afisare();
    return 0;
}