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

#define FORIT(it, v) for(vector<pair<int, int> > :: iterator it = (v).begin(); it != (v).end(); ++it)
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int max_n = 50005, inf = 0x3f3f3f3f;

vector<pair<int,int> > vertex[max_n];
priority_queue<pair<int, int> > pq;
bool viz[max_n];
int best[max_n];

int main() {
    int n, m;
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        in >> a >> b >> c;
        vertex[a].push_back(make_pair(b, c));
        //vertex[b].push_back(make_pair(a, c));
    }
    for (int i = 1; i <= n; ++i)
        best[i] = inf;
    pq.push(make_pair(0, 1));
    best[1] = 0;
    while (pq.size()) {
        int nod = pq.top().second;
        pq.pop();
        if (viz[nod])
            continue;
        viz[nod] = true;
        FORIT(it, vertex[nod])
            if (best[nod] + it->second < best[it->first]) {
                best[it->first] = best[nod] + it->second;
                pq.push(make_pair(-best[it->first], it->first));
            }
    }
    for (int i = 1; i <= n; ++i)
        best[i] = (best[i] == inf) ? (0) : (best[i]);
    for (int i = 2; i <= n; ++i)
        out << best[i] << " ";
    return 0;
}