#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
#include <bitset>

using namespace std;

const int NMAX = 50001;
const int INF = numeric_limits<int>::max();

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

class graf{
private:
    int nrNoduri, nrMuchii;
    vector<pair<int, int>> listaAdsiCosturi[NMAX];
    void BellmanFord(queue<int> &coadaNoduri, vector<int> &dist, vector<int> &nrRelaxari, bitset<NMAX> &inCoada, bool &rez);
public:
    graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
    void adaugaInListaAdsiCosturiOrientat(const int &nod1, const int &nod2, const int &cost);
    void afisareBellmanford();

};

void graf::adaugaInListaAdsiCosturiOrientat(const int &nod1, const int &nod2, const int &cost) {
    listaAdsiCosturi[nod1].push_back({nod2, cost});
}

void graf::afisareBellmanford() {
    vector<int> dist;
    queue<int> coadaNoduri;
    coadaNoduri.push(1);
    vector<int> nrRelaxari;
    bitset<NMAX> inCoada;
    inCoada[1] = true;
    nrRelaxari.resize(nrNoduri + 1, 0);
    dist.resize(nrNoduri + 1, INF);
    dist[1] = 0;
    bool eCircuitNegativ = false;
    BellmanFord(coadaNoduri, dist, nrRelaxari, inCoada, eCircuitNegativ);

    for (int i = 2; i <= nrNoduri; i++){
            fout << dist[i] << " ";
    }
}

void graf::BellmanFord(queue<int> &coadaNoduri, vector<int> &dist, vector<int> &nrRelaxari, bitset<NMAX> &inCoada, bool &rez) {
    while (!coadaNoduri.empty()){
        int front = coadaNoduri.front();
        coadaNoduri.pop();
        int distCrt = dist[front];
        int nrVecini = listaAdsiCosturi[front].size();

        for (int j = 0; j < nrVecini; j++) {
            int vecinCrt = listaAdsiCosturi[front][j].first;
            int costCrt = listaAdsiCosturi[front][j].second;

            if (distCrt + costCrt < dist[vecinCrt]) {
                dist[vecinCrt] = distCrt + costCrt;
                nrRelaxari[vecinCrt] += 1;

                if (nrRelaxari[front] == nrNoduri) {
                    rez = true;
                    return;
                }

                if (!inCoada[vecinCrt]){
                    inCoada[vecinCrt] = true;
                    coadaNoduri.push(vecinCrt);
                }
            }
        }
    }
}

int main() {
    int noduri, muchii;
    fin>> noduri >> muchii;
    graf G(noduri, muchii);
    for(int i = 0; i < muchii; i++){
        int n1, n2, cost;
        fin >> n1 >> n2 >> cost;
        G.adaugaInListaAdsiCosturiOrientat(n1, n2, cost);
    }
    G.afisareBellmanford();

    return 0;
}