#include <bits/stdc++.h>

using namespace std;

class comp{
public:
    bool operator ()(pair <int, int> &a, pair <int, int> &b){
        return a.second > b.second;
    }
};
priority_queue < pair <int , int>, vector < pair <int, int>>, comp> pq;

int dist[50001];
vector < pair <int, int>> graff [50001];
int visitate[50001];

int main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    int n, m, cost, x, y;
    f >> n >> m;
    for (int i = 2; i <= n; i++){
        dist[i] = (1 << 29);
    }
    for (int i = 1; i <= m; i++){
        f >> x >> y >> cost;
        graff[x].push_back(make_pair(y ,cost));
    }

    pq.push(make_pair(1, 1));
    visitate[1] =  1;
    while(pq.size()) {
        int nod = pq.top().first;
        int cost2 = pq.top().second;
        pq.pop();
        if (dist[nod] != cost2){
            continue;
        }
        for (auto x : graff[nod]) {
            if (dist[x.first] > x.second + dist[nod]) {
                dist[x.first] = x.second + dist[nod];
                pq.push({x.first, dist[x.first]});
            }
        }
    }

    for( int i = 2; i <= n; i ++){
        if (dist[i] == (1<<29)){
          g << 0 << " ";
        }
        else g << dist[i] << " ";
    }
    return 0;
}