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

#define pb push_back
#define dbg(x) cout << #x <<": " << x << "\n";
#define sz(x) ((int)x.size())

using ll = long long;

const string fn = "dijkstra";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

const int oo = 2e9;

int n, m;
int d[50005];
vector<pair<int, int> > g[50005];
priority_queue<pair<int, int>, vector<pair<int, int> > ,greater<pair<int, int> > > q;
bitset<50005> inq;
void dij(int nod){

    for (int i = 1; i <= n; ++i)
        d[i] = oo;

    d[nod] = 0;
    q.push({0, nod});
    inq[nod] = 1;

    while(!q.empty()){
        int nac = q.top().second;
        int w = q.top().first;
        q.pop();
        inq[nac] = 0;
        for(auto i : g[nac]){
            if(w + i.first < d[i.second] && !inq[i.second]){
                inq[i.second] = 1;
                d[i.second] = w + i.first;
                q.push({d[i.second], i.second});
            }
        }
    }
}

int main(){

    fin >> n >> m;
    while(m--){
        int x, y, w;
        fin >> x >> y >> w;
        g[x].pb({w, y});
    }


    dij(1);

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

        return 0;
}