#include <fstream>
#include <vector>
#include <set>

#define NMax 50001
#define inf (1<<30)
#define mp make_pair

using namespace std;

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

int n, m;
vector<int> V[NMax];
vector<int> C[NMax];
int cost[NMax];
set<pair<int, int> > q;

void read() {
    f>>n>>m;
    for (int i=1;i<=m;i++) {
        int a, b, p;
        f>>a>>b>>p;
        V[a].push_back(b);
        C[a].push_back(p);
    }
}

void solve() {
    for (int i=1;i<=n;i++)
        cost[i] = inf;
    cost[1] = 0;
    q.insert(q.begin(), mp(0, 1));

    while (!q.empty()) {
        pair<int, int> ex = *(q.begin());
        int c = ex.first;
        int node = ex.second;
        q.erase(q.begin());

        for (int i=0;i<V[node].size();i++) {
            int vecin = V[node][i];
            if (cost[vecin] > c + C[node][i]) {
                cost[vecin] = c+C[node][i];
                q.insert(q.end(), mp(cost[vecin], vecin));
            }
        }
    }
}

void output() {
    for (int i=2;i<=n;i++)
        if (cost[i] == inf)
            g<<0<<' ';
        else
            g<<cost[i]<<' ';
}

int main() {

    read();
    solve();
    output();

    f.close();
    g.close();

    return 0;
}