#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 50005;
const int INF = 2e9;

int dist[NMAX];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
vector<pair<int,int>> graph[NMAX];

void dijkstra() {

    pq.push({0,1});
    int node, cost;
    int next_node;
    int next_cost;
    while(!pq.empty()) {
        node = pq.top().second;
        cost = pq.top().first;
        pq.pop();

        if(cost > dist[node])
            continue;

        for(auto &vec : graph[node]) {
            next_node = vec.second;
            next_cost = vec.first;

            if(dist[node] + next_cost < dist[next_node]) {
                dist[next_node] = dist[node] + next_cost;
                next_cost = dist[next_node];
                pq.push({next_cost, next_node});
            }
        }
    }
}

int main() {

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

    int n, m;
    fin >> n >> m;
    for(int i = 2; i <= n; i++) {
        dist[i] = INF;
    }

    for(int i = 1; i <= m; i++) {
        int x,y,cost;
        fin >> x >> y >> cost;
        graph[x].emplace_back(cost, y);
    }

    dijkstra();

    for(int i = 2; i <= n; i++) {
        if(dist[i] == INF) {
            fout << 0 << " ";
        }
        else {
            fout << dist[i] << " ";
        }
    }

    fin.close();
    fout.close();
    return 0;
}