#include <bits/stdc++.h>

#define inf 1<<29
#define NMax 50005
#define pb push_back
#define mp make_pair

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m;
int dist[NMax];
vector<int> G[NMax];
vector<int> C[NMax];
set < pair<int, int> > H;

void read() {
    f>>n>>m;
    for (int i=2;i<=n;i++) dist[i] = inf;
    for (int i=1;i<=m;i++) {
        int a, b, c;
        f>>a>>b>>c;
        G[a].pb(b);
        C[a].pb(c);
    }
}

void dijk() {
    H.insert( mp(0, 1) );
    while (H.size() > 0) {
        int cost = ((*H.begin()).first);
        int node = ((*H.begin()).second);

        H.erase(H.begin());

        for (int i=0;i<G[node].size();i++) {
            int vecin = G[node][i];
            int muchie = C[node][i];
            if (dist[vecin] > muchie + cost) {
                dist[vecin] = muchie + cost;
                H.insert( mp(dist[vecin], vecin) );
            }
        }
    }
}

int main() {

    read();
    dijk();
    for (int i=2;i<=n;i++)
        g<<((dist[i] == inf) ? 0 : dist[i])<<' ';

    f.close(); g.close();
    return 0;
}