#include <fstream>
#define infinit 100000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, x, y, m , p , a[1001][1001], v[1001], d[1001], i, j;

int main()
{
    fin >> n >> m;
    for (i = 1; i <= n ; i ++){
        fin >> x >> y >> p;
        a[x][y] = p;
    }
    for (i = 1; i <= n; i ++)
        for (j = 1; j <= n; j ++)
            if (a[i][j] == 0)
                a[i][j] = infinit;

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

    d[1] = 0;
    v[1] = 1;
    d[0] = infinit;

    for (i = 1;i <= n ; i ++)

    for (int k = 1; k <= n ; k ++){
        int pmax = 0;
        for (i = 1; i <= n ; i ++)
            if (v[i] == 0 && d[i] < d[pmax])
                pmax = i;
        v[pmax] = 1;
        for (i = 1; i <= n ; i ++)
            if (v[i] == 0 && d[i] > d[pmax] + a[pmax][i])
                d[i] = d[pmax] + a[pmax][i];
    }
    for (i = 2; i <= n ; i ++)
        if (d[i] != infinit)
            fout << d[i] << " ";
        else
            fout << -1 << " ";
    return 0;
}