#include <fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n, k;
const int N = 10000, Infinit = 240000000;
int m[N][N];
int d[N];
bool vizitat[N];

void initialiazare() {
    in >> n >> k;
    int i, j;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            m[i][j] = Infinit;
    m[1][1] = 0;
    for (i=1; i<=n; i++)
        d[i] = Infinit;
    d[1] = 0;
}

void citire() {
    int i;
    for (i=1; i<=k; i++) {
        int a,b,c;
        in >> a >> b >> c;
        m[a][b] = c;
        if (a == 1)
            d[b] = c;
    }
}

void dij(int nodCurent) {
    vizitat[nodCurent] = true;
    int nodUrmator=0, minim = Infinit;
    int j;
    for (j=1; j<=n; j++) {
        if (m[nodCurent][j] + d[nodCurent] < d[j])
            d[j] = m[nodCurent][j] + d[nodCurent];
        if (!vizitat[j])
            if (d[j] < minim) {
                minim = d[j];
                nodUrmator = j;
            }
    }
    if (nodUrmator)
        dij(nodUrmator);
}

void afisare() {
    int i;
    for (i=2; i<=n; i++) {
        if (d[i])
            out <<d[i] <<" ";
        else
            out << "0 ";
    }
}

int main()
{
    initialiazare();
    citire();
    dij(1);
    afisare();
    return 0;
}