#include<iostream>
#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int mat[20000][20000],d[50001],viz[50001],n,m,i,j,k,ok,minim;
int dij()
{viz[1]=1;
 ok=1;
 while(ok)
 {minim=2000;
 for(i=1;i<=n;i++)
    if(viz[i]==0 && minim>d[i])
         {minim=d[i];
         k=i;
         }
  if(minim!=2000)
  {viz[k]=1;
      for(i=1;i<=n;i++)
      if(viz[i]!=1 && d[i]>d[k]+mat[k][i])
      d[i]=d[k]+mat[k][i];
  }
  else
  ok=0;
 }
}
int citire()
{   f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            mat[i][j]=2000;
            else
            mat[i][j]=0;
            int a,b,c;
            for(i=1;i<=m;i++)
            {f>>a>>b>>c;
             mat[a][b]=c;}
   for(i=1;i<=n;i++)
    d[i]=mat[1][i];
}
int main()
{
    citire();
    dij();
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
}