#include<fstream>
#include<iostream>
using namespace std;
int const maxx=(1<<30);
#define N 23000
int mat[N][N],d[N],viz[N],n,m,s;
//int t[N];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

void citire()
{
    int i,j,x,y,cost;
    in>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(i==j) mat[i][j]=0;
            else mat[i][j]=maxx;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>cost;
        mat[x][y]=cost;
    }
}

void dijkstra(int ns)
{
    int i,j,k,minn;
    for(i=1; i<=n; i++)
    {
        d[i]=mat[ns][i];
        //if((i!=ns) && (d[i]!=maxx))
            //t[i]=ns;
    }
    viz[ns]=1;
    for(k=1; k<n; k++)
    {
        minn=maxx;
        for(i=1; i<=n; i++)
            if(viz[i]==0 && d[i]<minn)
            {
                minn=d[i];
                j=i;
            }
        for(i=1; i<=n; i++)
            if(viz[i]==0)
            {
                if(d[i]>d[j]+mat[j][i])
                {
                    d[i]=d[j]+mat[j][i];
                    //t[i]=j;
                }
            }
        viz[j]=1;
    }
}

/*void drum(int i)
{
    if(t[i]) drum(t[i]);
    out<<i<<" ";
}*/

int main()
{
    citire();
    int s=1;
    dijkstra(s);
    for(int i=2; i<=n; i++)
        /*if(i!=s)
        {
            out<<s<<"->"<<i<<": ";
            drum(i);
            out<<"="<<d[i]<<endl;
        }*/
        out<<d[i]<<" ";
        return 0;
}