#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> list_a[50001];
vector<pair<int, int>> q;
int cost[50001];

bool compare(pair<int, int> x, pair<int, int> y) {
    return x.second > y.second;
}

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m;
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        int st, dr, cost;
        fin >> st >> dr >> cost;
        list_a[st].emplace_back(dr, cost);
        //list_a[dr].emplace_back(st, cost);
    }
    for(int i = 0; i <= n; i++) {
        cost[i] = -1;
    }
    int start, final;
    //fin >> start >> final;
    start = 1;
    q.emplace_back(start, 0);
    make_heap (q.begin(),q.end(), compare);
    while(!q.empty()) {
        pop_heap (q.begin(),q.end(), compare);
        pair<int, int> nodc = q.back();
        q.pop_back();
        if(cost[nodc.first] != -1) continue;
        cost[nodc.first] = nodc.second;
        for(auto i: list_a[nodc.first]) {
            if(cost[i.first] == -1) {
                q.emplace_back(i.first, cost[nodc.first] + i.second);
                push_heap (q.begin(),q.end(), compare);
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        if (cost[i]==-1) fout<<0<<" "; else fout << cost[i] << ' ';
    }
    return 0;
}