#include <fstream>
#include <vector>
#include <climits>
#include <queue>
#define dim 50001
using namespace std;
int n, m, i, j, a, b, c, x, d[dim], nod;
vector < pair <int, int> > g[dim];
bool viz[dim];
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
struct cmp {
    bool operator() (pair <int, int> &x, pair <int, int> &y) const {
        return x.second>y.second;
    }
};
priority_queue < pair <int, int>, vector < pair <int, int> >, cmp> q;

int main () {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>a>>b>>c;
        g[a].push_back({b, c});
    }

    for (i=2;i<=n;i++) {
        d[i]=INT_MAX;
    }

    q.push({1, 0});
    while (!q.empty()) {
        pair <int, int> p=q.top();
        if (viz[p.first]==1) {
            q.pop();
            continue;
        }
        nod=p.first;
        viz[nod]=1;
        for (i=0;i<g[nod].size();i++) {
            int vec=g[nod][i].first;
            int cost=g[nod][i].second;
            if (viz[vec]==0 && d[vec]>d[nod]+cost) {
                d[vec]=d[nod]+cost;
                q.push({vec, d[vec]});
            }
        }
    }
    for (i=2;i<=n;i++) {
        if (d[i]!=INT_MAX) {
            fout<<d[i]<<" ";
        } else
            fout<<0<<" ";
    }

    return 0;
}