#include <fstream>
#include <vector>
#include <queue>

#define c first
#define v second

using namespace std;

typedef pair<int, int> pii;

const int oo = 1000000000;
const int MaxN = 100005;

vector<pii> G[MaxN];
int N, D[MaxN];
priority_queue< pii, vector<pii>, greater<pii> > H;

void InitDijkstra(int Start) {
    for (int X = 1; X <= N; ++X)
        D[X] = oo;
    H.push(make_pair(0, Start));
}

void Dijkstra(int Start) {
    InitDijkstra(Start);
    while (!H.empty()) {
        pii X = H.top(); H.pop();
        if (D[X.v] != oo)
            continue;
        D[X.v] = X.c;
        for (vector<pii>::iterator Y = G[X.v].begin(); Y != G[X.v].end(); ++Y)
            if (D[Y->v] == oo)
                H.push(make_pair(X.c + Y->c, Y->v));
    }
}

void Read() {
    ifstream fin("dijkstra.in");
    int M; fin >> N >> M;
    for (; M; --M) {
        int X, Y, C; fin >> X >> Y >> C;
        G[X].push_back(make_pair(C, Y));
    }
}

void Print() {
    ofstream fout("dijkstra.out");
    for (int X = 2; X <= N; ++X)
        fout << (D[X] == oo ? 0 : D[X]) << " ";
    fout << "\n";
}

int main() {
    Read();
    Dijkstra(1);
    Print();
    return 0;
}