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

using namespace std;

#define maxN 50005
#define INF INT_MAX

class cmp {
public:
    bool operator() (pair <int, int> &lhs, pair <int, int> &rhs) {
        return lhs.second > rhs.second;
    }
};

int cost[maxN], N, M;
//bool viz[maxN];
vector <pair <int, int> > G[maxN];
typedef priority_queue <pair <int, int>, vector <pair <int, int> >, cmp> my_pc;
my_pc Q;

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

    f >> N >> M;

    for (int i = 0; i < M; ++i) {
        int x, y, c;
        f >> x >> y >> c;

        G[x].push_back(make_pair(y, c));
    }

    for (int i = 1; i <= N; ++i) {
        cost[i] = INF;
    }

    cost[1] = 0;
    Q.push(make_pair(1, 0));

    while(!Q.empty()) {
        int root = Q.top().first;
        int rootCost = Q.top().second;

//        viz[root] = true;
        Q.pop();

        for (unsigned int i = 0; i < G[root].size(); ++i) {
            int neighbor = G[root][i].first;
            int edgeCost = G[root][i].second;

            if (rootCost + edgeCost >= cost[neighbor] /*|| viz[neighbor]*/) {
                continue;
            }

            cost[neighbor] = rootCost + edgeCost;
            Q.push(make_pair(neighbor, cost[neighbor]));
        }
    }

    for (int i = 2; i <= N; ++i) {
        if (cost[i] == INF) {
            g << 0 << " ";
        } else {
            g << cost[i] << " ";
        }
    }

    return 0;
}