#include <fstream>
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
int a[1500][1500],d[1501],viz[1501],n,m;
void init();
void citire ()
{ int x,y,k;
    cin>>n>>m; init();
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>k;
        a[x][y]=k;
    } for(int i=1;i<=n;i++) d[i]=a[1][i];
}
void init ()
{
    for(int i=1;i<=n;i++)
    {
         for(int j=1;j<=n;j++)
            if(i!=j) a[i][j]=1001;
    }
    viz[1]=1;
}
void dijkstra()
{ int nod,minim;
    for(int i=1;i<n;i++)
    {
        minim=1001;
        for(int j=1;j<=n;j++)
        {
            if(viz[j]==0 && d[j]<minim) minim=d[j],nod=j;
        }
        if(minim==1001) break;viz[nod]=1;
        for(int j=1;j<=n;j++)
        {
            if(viz[j]==0)
                if(minim+a[nod][j]<d[j]) d[j]=minim+a[nod][j];
        }
    }
}
void afis ()
{
     for(int i=2;i<=n;i++)
     {
         if(d[i]==1001) d[i]=0;
         cout<<d[i]<<" ";
     }
}
int main()
{
    citire();
    dijkstra();
    afis();
    return 0;
}