#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
#define pb push_back

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

const int N = 50005;
const int oo = 0x3f3f3f3f;

int n, c[N];
vector<pii> e[N];

void read(), dijkstra();

int main(){
    read();
    dijkstra();
    for (int i = 2; i <= n; i++)
        fout << (c[i] == oo ? 0 : c[i])  << ' ';

    return 0;
}
void read(){
    int m; fin >> n >> m;
    while (m--){
        int a, b, k; fin >> a >> b >> k;
        e[a].pb({b, k});
    }
    memset(c, oo, sizeof c);
}
void dijkstra(){
    set<pii> s; s.insert({0, 1}); c[1] = 0;
    while (!s.empty()){
        int cst, from; 
        tie(cst, from) = *s.begin();
        s.erase(s.begin());
        for (auto it: e[from]){
            int to, cm; tie(to, cm) = it;
            if (cm + cst < c[to]){
                if (c[to] == oo)
                    s.erase({c[to], to});
                c[to] = cst + cm;
                s.insert({c[to], to});
            }
        }
    }
}

//13:31