#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int NMAX = 50000,
          INF = (1 << 30);
int N, M, C[NMAX+1];
bool viz[NMAX+1];

struct nod {
    int x, costNod;
    bool operator <(const nod &n) const {
        return costNod > n.costNod;
    }
};

struct muchie {
    int y, costMuchie;
};

vector <muchie> G[NMAX+1];
priority_queue<nod> Q;

void citire() {
    f >> N >> M;
    //
    int xx, yy, cc;
    for (int i=1; i<=M; i++) {
        f >> xx >> yy >> cc;
        G[xx].push_back({yy, cc});
    }
    //
    for (int i=1; i<=N; i++)
        C[i] = INF;
}

void Dijkstra(int start) {
    C[start] = 0;
    Q.push({start, 0});
    while (!Q.empty()) {
        nod crt = Q.top();
        Q.pop();
        if (!viz[crt.x]) {
            viz[crt.x] = 1;
            //
            for (const auto &mm : G[crt.x])
                if (C[mm.y] > mm.costMuchie + crt.costNod) {
                    C[mm.y] = mm.costMuchie + crt.costNod;
                    Q.push({mm.y, C[mm.y]});
                }
        }
    }
}

void afis() {
    for (int i=2; i<=N; i++)
        if (C[i] == INF)
            g << "0 ";
        else
            g << C[i] << ' ';
}

int main()
{
    citire();
    Dijkstra(1);
    afis();
    f.close();
    g.close();
    return 0;
}