#include<bits/stdc++.h>
using namespace std;

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

#define pii pair<int, int>

int n, m;
vector<pii> G[50005];
vector<int> D;

struct comp{
    bool operator()(pii a, pii b){
        return a.second < b.second;
    }
};

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

    for(;m--;){
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y, c));
    }

    D.resize(n + 1, 1e9);
    D[1] = 0;

    priority_queue<pii, vector<pii>, comp> PQ;
    PQ.push({1, 0});

    while(!PQ.empty()){
        int node = PQ.top().first;
        PQ.pop();

        for(pii p : G[node])
        if(D[p.first] > D[node] + p.second){
            D[p.first] = D[node] + p.second;
            PQ.push({p.first, D[p.first]});
        }
    }

    for(int i = 2; i <= n; ++i)
        if(D[i] != (int)1e9)
            fout << D[i] << ' ';
        else
            fout << "0 ";
}