#include <bits/stdc++.h>
#define I 0x3f3f3f3f
#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];
vector<H>v[N+1];
main() {
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
 
    int n, m;
    f >> n >> m;
 
    int i, j, c;
    for (; m; 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 (auto 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?0:D[i]) << ' ';
}