#include<bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int Nmax = 50005;
const int inf = INT_MAX;

struct graf {

    int nod, cost;
};

list<graf> G[Nmax];
list<graf>::iterator it;
bitset<Nmax> viz;
int dist[Nmax];
int n, m, x, y, c, nod_curent, cost_nou, nod_nou, i;

struct cmp {

    bool operator() (const int &a, const int &b) {

        return dist[a] > dist[b];
    }
};

priority_queue<int, vector<int>, cmp> pq;

void citire() {

    f >> n >> m;

    while(m--) {

        f >> x >> y >> c;

        G[x].push_back({y, c});
    }
}

void Dijkstra() {

    for(i = 1; i <= n; ++i)
        dist[i] = inf;

    dist[1] = 0;

    viz[1] = true;
    pq.push(1);

    while(!pq.empty()) {

        nod_curent = pq.top();
        pq.pop();

        for(it = G[nod_curent].begin(); it != G[nod_curent].end(); ++it) {

            cost_nou = it->cost;
            nod_nou = it->nod;

            if(dist[nod_nou] > dist[nod_curent] + cost_nou) {

                dist[nod_nou] = dist[nod_curent] + cost_nou;

                if(!viz[nod_nou]) {

                    pq.push(nod_nou);
                    viz[nod_nou] = true;
                }
            }
        }
    }
}

int main() {

    citire();
    Dijkstra();

    for(i = 2; i <= n; ++i)
        if(dist[i] == inf)
            g << 0 << ' ';
        else
            g << dist[i] << ' ';
}