#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

#define inf 1e9

struct Muchie {
    int x, y, dist;
};
struct Node {
    int x, dist;
};
bool operator<(const Muchie&a, const Muchie&b) {
    return a.dist < b.dist;
}
bool operator<(const Node&a, const Node&b) {
    if (a.dist == b.dist) {
        return a.x < b.x;
    }
    return a.dist < b.dist;
}

typedef vector<vector<Node>> ListaVecini;

vector<int> Dijkstra(int nod, int n, const ListaVecini& vecini) {

    vector<int> dist(n, inf);
    set<Node> S;

    dist[nod] = 0;
    for (const Node& vec : vecini[nod])
        S.emplace(vec.x, vec.dist);

    while (!S.empty()) {
        Node node = *S.begin();
        S.erase(S.begin());

        if (dist[node.x] != inf)
            continue;
        dist[node.x] = node.dist;

        for (const Node& vec : vecini[node.x]) {
            if (dist[vec.x] != inf)
                continue;

            S.emplace(vec.x, node.dist + vec.dist);
        }
    }

    return dist;
}

int main() {
    int n, m;
    in>> n >> m;
    ListaVecini vecini(n);
    for (int i = 0; i < m; i++) {
        Muchie muc;
        in>> muc.x >> muc.y >> muc.dist;
        muc.x--; muc.y--;
        vecini[muc.x].emplace_back(muc.y, muc.dist);
        //vecini[muc.y].emplace_back(muc.x, muc.dist);
    }

    int nod = 0;
    vector<int> dist = Dijkstra(nod, n, vecini);

    for (int i = 0; i < n; i++) {
        if (i == nod)
            continue;

        if (dist[i] == inf)
            out << "0 ";
        else
            out << dist[i] << " ";
    }
    return 0;
}