#include <bits/stdc++.h>

using namespace std;

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

int n, m, d[50001], p[50001];
vector<pair<int, int>> a[50001];

void dijkstra(int u){
    for(int i = 1; i<=n; i++)
        d[i] = INT_MAX, p[i] = -1;

    d[u] = 0;
    set<pair<int, int>> q;
    q.insert({u, 0});
    while(!q.empty()){
        int s = q.begin()->first;
        q.erase(q.begin());

        for(auto it : a[s]){
            int nodnou = it.first;
            int lennou = it.second;

            if(d[s] + lennou < d[nodnou]){
                q.erase({d[nodnou], lennou});
                d[nodnou] = d[s] + lennou;
                p[nodnou] = s;
                q.insert({nodnou, d[nodnou]});
            }
        }
    }
}

int main(){
    fin >> n >> m;

    int x, y, len;
    while (m--){
        fin >> x >> y >> len;
        a[x].push_back(make_pair(y, len));
    }
    

    dijkstra(1);

    for(int i = 2; i<=n; i++)
        fout << d[i] << ' ';

    return 0;
}