#include <fstream>
#include<climits>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int i,D[1000],T[1000],S[1000],n,x,y,r,z,a[1000][1000],j,ok1,k,ok2,minim,m;
int main()
{fin>>n>>m;
for(i=1;i<=m;i++)
{fin>>x>>y>>z;
    a[x][y]=z;}
    r=1;
    for(i=1;i<=n;i++)
if(i!=r) {
    if(a[r][i]) D[i]=a[r][i];
    else D[i]=INT_MAX/2;
}
else D[i]=0;
S[r]=1;
for(i=1;i<=n;i++)
    if(a[r][i]) T[i]=r;
    else T[i]=0;
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(!a[i][j]) a[i][j]=INT_MAX/2;

  while(ok1==0&&ok2==0)
  {minim=INT_MAX;
      for(i=1;i<=n;i++)
  if(S[i]==0) if(D[i]<minim) {minim=D[i];k=i;}
      S[k]=1;
      for(i=1;i<=n;i++)
        if(S[i]==0)
        if(D[k]+a[k][i]<D[i]) {D[i]=D[k]+a[k][i];T[i]=k; }
        ok1=1; ok2=1;
  for(i=1;i<=n;i++)
  if(S[i]==0) {ok1=0; if(D[i]!=INT_MAX/2) ok2=0; }
  }

    for(i=2;i<=n;i++)
    {if(D[i]!=INT_MAX/2)
        fout<<D[i]<<' ';
        else fout<<"0"<<' ';
    }


    return 0;
}