#include <bits/stdc++.h>

using namespace std;

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

const int Maxx = 50005, inf = 20005;
int N, M, d[Maxx];
vector < pair <int, int> > W[Maxx];
priority_queue < pair <int, int> > Q;

void dijkstra(int node) {
    for(int i = 1; i <= N; i++) d[i] = inf;
    d[node] = 0;
    Q.push({node, 0});
    while(!Q.empty()) {
        int nod = Q.top().first;
        Q.pop();
        for(int i = 0; i < W[nod].size(); i++) {
            int vecin = W[nod][i].first;
            int cost  = W[nod][i].second;
            if(d[nod] + cost < d[vecin]) {
                d[vecin] = d[nod] + cost;
                Q.push({vecin, d[vecin]});
            }
        }
    }
}

int main() {
    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] << " ";
}