#include <bits/stdc++.h>

using namespace std;

const int Maxx = 50005, inf = 20005;
int N, M, d[Maxx];

struct Node {
    int node, cost;
}n, v;

bool operator < (const Node &x, const Node &y) {
    return x.cost > y.cost;
}

vector < Node > W[Maxx];
priority_queue < Node > Q;

void dijkstra(int node) {
    for(int i = 1; i <= N; ++i)
        d[i] = inf;
    d[node] = 0;
    n.node = 1;
    n.cost = 0;
    Q.push(n);
    while(!Q.empty()) {
        n = Q.top();
        Q.pop();
        if(d[n.node] < n.cost)continue;
        for(unsigned int i = 0; i < W[n.node].size(); ++i) {
            if(d[W[n.node][i].node] == -1 || d[W[n.node][i].node] > n.cost + W[n.node][i].cost) {
                d[W[n.node][i].node] = n.cost + W[n.node][i].cost;
                v.node = W[n.node][i].node;
                v.cost = d[W[n.node][i].node];
                Q.push(v);
            }
        }
    }
}

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> N >> M;
    int x, y, c;
    while(M--) {
        fin >> x >> y >> c;
        W[x].push_back({y, c});
    }
    dijkstra(1);
    for(int i = 2; i <= N; ++i)
        (d[i] == inf) ? fout << "0 " : fout << d[i] << " ";
}