#include <bits/stdc++.h>
#define N 50000
using namespace std;
struct H {
  int n,d;
  bool operator<(const H&x)const{return d>x.d;}
};
int D[N+1],n,m,i,j,c,I=0x3f3f3f3f;
vector<H>v[N+1];
main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    f >> n >> m;
    while(m--)
        f >> i >> j >> c,
        v[i].push_back({j,c});
 
    fill(D+2,D+n+1,I);
    priority_queue<H>q;
    q.push({1,0});
 
    while (q.size()) {
        H h=q.top();
        q.pop();
 
        if (D[h.n] == h.d)
            for (H t: v[h.n])
                if (D[t.n] > h.d + t.d)
                    D[t.n] = h.d + t.d,
                    q.push({t.n, D[t.n]});
    }
 
    for (i=2; i<=n; ++i)
        g << (D[i]^I?D[i]:0) << ' ';
}