#include <bits/stdc++.h>

using namespace std;

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

bool ok;

int n, m, i, a, b, c, poz, vecin;
int f[50005], v[50005];

vector < pair <int, int> > L[50005];

int main(){
    fin >> n >> m;
    for (i=1; i<=m; i++){
        fin >> a >> b >> c;
        L[a].push_back ({b, c});
    }
    v[1] = 0;
    for (i=2; i<=n; i++){
        v[i] = INT_MAX;
    }
    while (1){
        m = INT_MAX; /// folosesc m ca sa nu mai declar alta variabila
        ok = 0;
        for (i=1; i<=n; i++){
            if (f[i] == 0 && v[i] < m){
                m = v[i];
                poz = i;
                ok = 1;
            }
        }
        if (ok == 0)
            break;
        f[poz] = 1;
        for (i=0; i<L[poz].size(); i++){
            vecin = L[poz][i].first;
            v[vecin] = min (v[vecin], v[poz] + L[poz][i].second);
        }
    }
    for (i=2; i<=n; i++){
        if (v[i] == INT_MAX){
            fout << 0 << " ";
        }
        else{
            fout << v[i] << " ";
        }
    }
    return 0;
}
//40p