#include <fstream>
#include <vector>
#include <climits>
#include <queue>
using namespace std;
int n, m, x, y, dist, d[50001], Min, nod, cost, p, i, j, nv;
vector < pair <int, int> > g[50001];
bool viz[50001];
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>>x>>y>>dist;
        g[x].push_back({y, dist});
    }

    ///d[i]=distanta de la 1 la nodul i

    d[1]=0;
    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++) {
            nv=g[nod][i].first;
            cost=g[nod][i].second;
            if (viz[nv]==0 && d[nv]>d[nod]+cost) {
                d[nv]=d[nod]+cost;
                q.push({nv, d[nv]});
            }
        }
    }
    for (i=2;i<=n;i++) {
        if (d[i]!=INT_MAX) {
            fout<<d[i]<<" ";
        } else
            fout<<0<<" ";
    }

    return 0;
}