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

using namespace std;

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

bool compare(int x, int y) {
    return cost[x] > cost[y];
}

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].push_back(make_pair(dr, cost));
        list_a[dr].push_back(make_pair(st, cost));
    }
    for(int i = 0; i <= n; i++) {
        cost[i] = -1;
    }
    int start, final;
    //fin >> start >> final;
    start = 1;
    cost[start] = 0;
    q.push_back(start);
    make_heap (q.begin(),q.end(), compare);
    while(!q.empty()) {
        pop_heap (q.begin(),q.end(), compare);
        int nodc = q.back();
        q.pop_back();
        for(auto i: list_a[nodc]) {
            if(cost[i.first] == -1) {
                cost[i.first] = cost[nodc] + i.second;
                q.push_back(i.first);
                push_heap (q.begin(),q.end(), compare);
            }
        }
    }
    for(int i = 2; i <= n; i++) {
        fout << cost[i] << ' ';
    }
    return 0;
}