#include <iostream>
#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m,mc[20000][20000], drum[50000];
int u[50000], d[50000];

void dijkstra(int sursa)
{
    int INF = 1001;
    int i, min, nod;
    d[sursa] = 0;

    while (1){
        min = INF;
        nod = -1;
        for(i=1; i<=n; i++)
            if(u[i] == 0 && min > d[i] ){
                min = d[i];
                nod = i;
            }
        if(min == INF)
            break;

        u[nod] = 1;

        for(i=1; i<=n; i++)
            if(d[i] > d[nod] + mc[nod][i]){
                d[i] = d[nod] + mc[nod][i];
                drum[i] = nod;
        }

    }

    for(i=2; i<=n; i++)
            g<<d[i]<<" ";
        g<<"\n";
}

int main()
{
    int a, b, c, i, j;
    f>>n>>m;

    int INF = 10000;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            mc[i][j] = INF;

    for(i=1; i<=n; i++)
        d[i] = INF;
    for(i=1; i<=m; i++){
        f>>a>>b>>c;
        mc[a][b] = c;
    }

    int s = 1;
    dijkstra(s);

    return 0;
}