#include <iostream>
#include <fstream>
#include <set>
#include <queue>
#define INF 0xffffff

using namespace std;

vector <vector <pair <int, int> > > mat;
vector <int> cost;
vector <int> visited;
set < pair <int, int> > q;/// x->y with c: <c, <x, y> >

int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    int n, m, x, y, c, i;
    in >> n >> m;
    cost.resize (n+1, INF);cost[1] = 0;
    visited.resize (n+1, 0);cost[1] = 1;
    mat.resize (n+1);

    for (i = 0; i < m; ++i) {
        in >> x >> y >> c;
        mat[x].push_back (make_pair(y, c));
    }
    vector <pair <int, int> > ::iterator k;
    for (k = mat[1].begin(); k != mat[1].end(); ++k) {q.insert (make_pair (k->second, k->first));}

    pair <int, int> now;
    while (!q.empty()) {
        now = *q.begin();
        c = now.first; /// cost[x] + c
        y = now.second;

        if (cost[y] > c) {
            cost[y] = c;
            visited[y] = 1;
            for (k = mat[y].begin(); k != mat[y].end(); ++k) {
                if (!visited[k->first]) {q.insert (make_pair (c + k->second, k->first));}
            }
        }

        q.erase (now);
    }

    for (i = 2; i <= n; ++i) {out << ((cost[i] == INF) ? 0 : cost[i]) << " ";}

    return 0;
}