#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int st, dr, c;
vector<pair<int,int>> v[50001];
int mark[50001];

void dijkstra(int start){
    mark[start] = 1;
    priority_queue<pair<int,int>> pq;
    pq.push({0, start});
    while(!pq.empty()){
        int cost_curr = pq.top().first;
        int nod_curr = pq.top().second;
        pq.pop();
        for (int i = 0; i < v[nod_curr].size(); i++){
            int vecin = v[nod_curr][i].first;
            int cost = v[nod_curr][i].second;
            if (!mark[vecin] || mark[nod_curr] + cost < mark[vecin]){
                mark[vecin] = mark[nod_curr] + cost;
                pq.push({mark[vecin], vecin});
            }
        }
    }
}

int main(){
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>st>>dr>>c;
    v[st].push_back({dr, c});
}
dijkstra(1);
for (int i = 2; i <= n; i++){
    fout << mark[i] - 1 << " ";
}
// complexitate O(mlogn)
    return 0;
}