#include <fstream>
#include <iostream>
#include <iomanip>

#define MARE 1000

using namespace std;

// n - numarul de noduri
// m - numarul de muchii
// s - sursa
// a - matricea costurilor
// d - distantele de la sursa la noduri
int i, n, m, l, c, s, a[1001][1001], d[1001];
bool sel[10];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void dijkstra (int s) {
    int min, nmin, dn;

    for (int i = 1; i <= n; i++)
        d[i] = a[s][i];
    sel[s] = true; // Sursa este selectata.
    d[s] = 0;
    for (int pas = 2; pas <= n; pas++) { // Alegem nodul neselectat, situat la distanta minima de sursa.
        min = MARE;
        for (i = 1; i <= n; i++)
            if (not sel[i])
                if (d[i] < min) {
                    min = d[i]; nmin = i; // nmin devine roz
                }
        sel[nmin] = true;
        for (i = 1; i <= n; i++)
            if (not sel[i]) {
                dn = d[nmin] + a[nmin][i];
                if (dn < d[i])
                    d[i] = dn;
            }
    }
}

int main()
{
    fin >> n >> m;
    for (l = 1; l <= n; l++)
        for (c = 1; c <= n; c++)
            a[l][c] = MARE;
    for (i = 1; i <= m; i++)
    {
        fin >> l >> c;
        fin >> a[l][c];
        //a[c][l] = a[l][c];
    }
    dijkstra(1);
    for (i = 2; i <= n; i++)
        fout << d[i] << ' ';
    return 0;
}