#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, 0));
    visitate[1] =  1;
    while(pq.size()) {
        int nod = pq.top().first;
        pq.pop();

        for (auto x : graff[nod]) {
            int nextN = x. first;
            int nCost = x.second;

            if (dist[nextN] > (dist[nod] + nCost)) {
                dist[nextN] = (dist[nod] + nCost);
                pq.push({nextN, dist[nextN]});
            }
        }
    }

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