#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];
bool visited[50001];

void dijkstra(int start){
    mark[start] = 1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({1, start});
    while(!pq.empty()){
        int cost_curr = pq.top().first;
        int nod_curr = pq.top().second;
        pq.pop();
        if (cost_curr != mark[nod_curr] || visited[nod_curr] == 1)
            continue;
        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});
            }
        }
        visited[nod_curr] = 1;
    }
}

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++){
    if (!mark[i])
        fout << 0 << " ";
    else
        fout << mark[i] - 1 << " ";
}
// complexitate O(mlogn)
    return 0;
}