#include <iostream>
#include<fstream>


using namespace std;
ifstream fi("dijkstra.in");
ofstream  fo("dijkstra.out");

int a[50000][50000],n,m,D[50000];

void bordare()
{
int i,j;
for(i=1;i<=n;i++)
{

for(j=1;j<=n;j++)
 if(i!=j)
a[i][j]=1001;

}
}
void citire()
{int i,e,d,c;
fi>>n>>m;
    for(i=1;i<=m;i++)
     {
       fi>>e>>d>>c;
        a[e][d]=c;
      }
}
int main()
{
  int i,j;
      bordare();
      citire();
      for(i=1;i<=n;i++)
       D[i]=1001;
  for(i=2;i<=n;i++)
     if((a[1][i]!=1001)&&(a[1][i]!=0))
       D[i]=a[1][i];

  for(i=2;i<=n;i++)
   for(j=2;j<=n;j++)
     if((a[i][j]!=1001)&&(a[i][j]!=0))
     if(a[i][j]+D[i]<D[j])
          D[j]=a[i][j]+D[i];



  for(i=2;i<=n;i++)
    fo<<D[i]<<" ";
    return 0;

}