#include <fstream>
#define INF 2000000000
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int n,m;
int A[1001][1001];
int D[1001];
int VIZ[1001];
int x,y,l,s;
int main()
{
    fi>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            A[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        fi>>x>>y>>l;
        A[x][y]=l;
    }
    for(int i=1;i<=n;i++)
        D[i]=INF;
    for(int i=1;i<=n;i++)
        if(A[1][i]<INF)
            D[i]=A[1][i];
    for(int i=1;i<=n;i++)
    {
        int mn=INF,pmn;
        for(int j=1;j<=n;j++)
            if(mn>D[j] && VIZ[j]==0)
                mn=D[j],pmn=j;
        VIZ[pmn]=1;
        for(int j=1;j<=n;j++)
            if(A[pmn][j]<INF)
                D[j]=min(D[j],D[pmn]+A[pmn][j]);
                /*
        for(int j=1;j<=n;j++)
            fo<<D[j]<<" ";
        fo<<"\n";
        */
    }
    for(int i=2;i<=n;i++)
        fo<<D[i]<<" ";
    fi.close();
    fo.close();
    return 0;
}