#include <iostream>
#include <fstream>
#define oo 19999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int A[22001][22001],n,m,i,j,D[22001],T[22001],x,y,z,minim,poz,ST[22001];
void citire()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
         A[i][j]=oo;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        A[x][y]=z;
    }
}
void dijkstra()
{
    ST[1]=1;
    for(i=2;i<=n;i++)
    {
       D[i]=A[1][i];
       if(D[i]<oo)
        T[i]=1;
    }
    for(i=1;i<=n-1;i++)
    {
        minim=oo;
        for(j=1;j<=n;j++)
            if(D[i]<minim && ST[j]==0)
            {
                minim=D[i];
                poz=i;
            }
            ST[poz]=1;
        for(j=1;j<=n;j++)
            if(D[j]>D[poz]+A[poz][j] && ST[j]==0)
            {
                D[j]=D[poz]+A[poz][j];
                T[j]=poz;
            }
    }
}
void afis()
{
    for(i=2;i<=n;i++)
        fout<<D[i]<<" ";
}
int main()
{
    citire();
    dijkstra();
    afis();
    return 0;
}