#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <set>

using namespace std;

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

#define NMAX 50005
#define INF 1000000000

int n, m;
vector<pair<int, int>> G[NMAX];
int d[NMAX],prec[NMAX];
set<pair<int,int>> s;

void citire() {
    f >> n >> m;
    int nod1, nod2, cost;
    for (int i = 0; i < m; i++) {
        f >> nod1 >> nod2 >> cost;
        G[nod1].push_back({nod2, cost});
    }
}

void initializare()
{
    for (int i = 1; i <= n; i++)
        d[i] = INF;
}

void vizitare_nod(int x) {
    for (auto &nod: G[x])
        if (d[x] + nod.second < d[nod.first]) {
            if(d[nod.first]!=INF)
                s.erase({d[nod.first],nod.first});
            d[nod.first] = d[x] + nod.second;
            prec[nod.first] = x;
            s.insert({d[nod.first], nod.first});
        }
}
void parcurgere() {
    d[1] = 0;
    prec[1] = -1;
    s.insert({0, 1});
    while (!s.empty()) {
        pair<int,int> nod = *s.begin();
        s.erase(nod);
        vizitare_nod(nod.second);
    }
}
void afisare() {
    for (int i = 2; i <= n; i++) {
        if (d[i] == INF)
            g << 0 << ' ';
        else
          g << d[i] << ' ';
    }
}

int main() {
    citire();
    initializare();
    parcurgere();
    afisare();
    return 0;
}