#include <bits/stdc++.h>
#define NMAX 50005
#define INF 0x3F3F3F3F
using namespace std;

vector <pair <int, int>> G[NMAX];
int dist[NMAX];

int main (void) {
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");
    int n, m, i, j, c;
    fin >> n >> m;
    for (; m; m--) {
        fin >> i >> j >> c;
        G[i].push_back(make_pair(j, c));
    }

    memset (dist, INF, sizeof(dist));
    dist[1]=0;
    set <pair <int, int>> h;
    h.insert(make_pair(0, 1));

    int nod, d, to, cost;
    while (!h.empty()) {
        nod=h.begin()->second;
        d=h.begin()->first;
        h.erase(h.begin());

        for (auto it: G[nod]) {
            to=it.first;
            cost=it.second;
            if (dist[nod]+cost<dist[to]) {
                if (dist[to]!=INF)
                    h.erase(make_pair(dist[to], to));
                dist[to]=dist[nod]+cost;
                h.insert(make_pair(dist[to], to));
            }
        }
    }

    for (i=2; i<=n; i++)
        fout << (dist[i]==INF?0:dist[i]) << ' ';
    return 0;
}