#include <fstream>
#include <vector>
#include <set>

#define DIM 50010
#define INF DIM*1000

using namespace std;

vector < pair<int, int> > L[DIM];
set < pair<int, int> > s;

int V[DIM], D[DIM], i, x, y, c, n, m, k;

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

int main() {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        L[x].push_back( make_pair(y, c) );
    }

    for (i=1;i<=n;i++) {
        D[i] = INF;
    }
    D[1] = 0;

    s.insert(make_pair(0,1));
    /// in s tinem perechi (cost, nod) doar pentru nodurile
    /// nealese inca si actualizate macar o data
    /// in paralel tinem distantele minime la noduri si in D

    /// perechile din ste sunt (D[nod], nod)

    while (!s.empty()) {
        k = s.begin()->second;
        s.erase( s.begin() );
        /// extragem in o(1) minimul (inlocuieste forul de aflare a minimului)
        for (i=0;i<L[k].size();i++)
            if (D[ L[k][i].first ] > D[k] + L[k][i].second) {
                /// daca se actualizeaza D al unui vecin, in cazul in care el este in set
                /// (daca anterior mai fusese actualizat) stergem ferechea formata cu vecniul cost si nod
                /// apoi adaugam parechea cu costul actualizat si nod
                s.erase (  make_pair(D[ L[k][i].first ], L[k][i].first) );
                D[ L[k][i].first ] = D[k] + L[k][i].second;
                s.insert (  make_pair(D[ L[k][i].first ], L[k][i].first) );
            }
    }

    for (i=2;i<=n;i++)
        if (D[i] == INF)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";

}