#include <iostream>
#include <fstream>
#define inf 1e9

using namespace std;



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

int n, m, i, j, cost[10001][10001], d[50001], x, y, c, viz[50001];

int main()
{   f >> n >> m;

    for ( i = 1; i <= n; i++ ){
        f >> x >> y >> c;
        cost[x][y] = c;
    }


    for ( i = 1; i <= n; i++ ){
        d[i] = inf;
    }

    d[1] = 0;
    for ( i = 1; i <= n; i++ ){

        int minim = inf, nod;
        for ( j = 1; j <= n; j++ )
        if ( viz[j] == 0 && d[j] < minim ){
            nod = j;
            minim = d[j];
        }
        viz[nod] = 1;
        for ( j = 1; j <= n; j++ ){
           if(cost[nod][j]!=0)
            if ( d[j] > d[nod] + cost[nod][j] )
                d[j] = d[nod] + cost[nod][j];
        }
    }
    for ( i = 2; i <= n; i++ )
        g << d[i] << " ";



    return 0;
}