#include <fstream>
#include <vector>
#include <list>
using namespace std;


const int kInf = 50000, kNMax = 50010, kCostM = 50010;
int n, m, dist[kNMax];
vector <pair <int,int> > G[kNMax];
list <int> noduri[kCostM];
list <int> :: iterator poz[kNMax];


void Citire () {
    ifstream in ("dijkstra.in");
    int n1, n2, c;
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> n1 >> n2 >> c;
        G[n1].push_back(make_pair(n2, c));
    }
}

void Initializare() {
    int nod = 2;
    for( int i = 2; i <= n; ++i) {
        dist[i] = kInf;
        noduri[kInf].push_back(i);
    }
    for (list <int> :: iterator i = noduri[kInf].begin(); i != noduri[kInf].end(); ++i) {
        poz[nod] = i;
        nod++;
    }
    noduri[0].push_back(1);
    poz[1] = noduri[0].begin();

}

void Dijkstra() {
    int nod, vecin, cost;
    for (int i = 0; i < kInf; i++) {
        while (!noduri[i].empty()){
            nod = noduri[i].front();
            noduri[i].pop_front();
            for ( int j = 0; j < G[nod].size(); ++j){
                vecin = G[nod][j].first;
                cost = G[nod][j].second;
                if (dist[vecin] > dist[nod] + cost) {
                    noduri[dist[vecin]].erase(poz[vecin]);
                    dist[vecin] = dist[nod] + cost;
                    noduri[dist[vecin]].push_back(vecin);
                    poz[vecin] = --noduri[dist[vecin]].end();
                }
            }
        }
    }
}


void Solve() {
    Initializare();
    Dijkstra();
}

void Afisare() {
    ofstream out("dijkstra.out");
    for (int i = 2; i <= n; ++i)
        if (dist[i] == kInf)
            out << 0 << ' ';
        else
            out << dist[i] << ' ';
    out << '\n';
    out.close();
}

int main() {
    Citire();
    Solve();
    Afisare();
    return 0;
}