#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
 
#define INF             (2147483647 - 20000)
#define MAX_NODES       50001
 
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;
}