#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define INF             (2147483647 - 20000)
#define MAX_NODES       500001

using namespace std;

int sol[MAX_NODES];
vector<pair<int, int> > graf[MAX_NODES];
vector<int> q;
int n, m, x, y, w, heap_index = 0;

bool comp(int &x, int &y)
{
    return sol[x] > sol[y] ? true : false;
}

void dijkstra()
{
    int node;
    q.push_back(1);
    for (int i = 2; i <= n; i++) {
        sol[i] = INF;
        q.push_back(i);
    }

    while (heap_index < q.size()) {
        make_heap(q.begin() + heap_index, q.end(), comp);
        node = q[heap_index];
        heap_index++;

        for (const auto& it : graf[node])
            if (sol[node] + it.second < sol[it.first]) 
                sol[it.first] = sol[node] + it.second;
    }
}

int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> w;
        graf[x].push_back(make_pair(y, w));
    }

    dijkstra();

    for (int i = 2; i <= n; i++) {
        if (sol[i] == INF)
            out << 0 << ' ';
        else
            out << sol[i] << ' ';
    }

    return 0;
}