#include <fstream>
#include <queue>
using namespace std;

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

const int N = 5e4 + 5, oo = 1e9;

vector <pair <int, int> > g[N];
int m, n, d[N];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > H;

int main() {
    fin >> n >> m;
    for (int i = 2; i <= n; ++i)
        d[i] = oo;
    for (int x, y, c, i = 0; i < m; ++i) {
        fin >> x >> y >> c;
        g[x].push_back (make_pair (y, c));
    }
    H.push (make_pair (0, 1));
    while (H.size()) {
        int cost = H.top().first, x = H.top().second; H.pop();
        if (d[x] < cost)
            continue;
        for (vector <pair <int, int> > :: iterator it = g[x].begin(); it != g[x].end(); ++it)
            if (d[it->first] > cost + it->second) {
                d[it->first] = cost + it->second;
                H.push (make_pair (cost + it->second, it->first));
            }
    }
    for (int i = 2; i <= n; ++i)
        fout << ((d[i] != oo) ? d[i] : 0) << " ";
}