#include <bits/stdc++.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define NMAX 50000
priority_queue <pair<int,int> > Q;

vector <pair<int,int> > G[NMAX+5];
int N, M, Use[NMAX+5], D[NMAX+5];
int oo = 100000000;
void Read() {
    in >> N >> M;
    int x, y, c;
    for(int i = 0; i < M; i++) {
        in >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
}

int find_min() {
    while(Use[Q.top().second])
        Q.pop();
    int res = Q.top().second;
    Q.pop();
    return res;
}

void Dijkstra () {
    for (int i = 2; i <= N; i++)
        D[i] = oo;

    for (int i = 1; i <= N; i++)
        Q.push(make_pair(-D[i], i));

    for (int i = 1; i <= N; i++) {
            int Nod = find_min();
        Use[Nod] = 1;

        for (int i = 0; i < G[Nod].size(); i++) {
            int Vecin = G[Nod][i].first, Cost = G[Nod][i].second;
            if(D[Vecin] > D[Nod]+Cost) {
                D[Vecin] = D[Nod] + Cost;
                Q.push(make_pair(-D[Vecin], Vecin));
            }
        }
    }
}

void Print() {
    for (int i = 2; i <= N; i++) {
        if (D[i] == oo)
            D[i] = 0;
        out << D[i] << " ";
    }

    out << '\n';
}


int main () {
    Read();
    Dijkstra();
    Print();
}