#include <cstdio>
#include <cstring>
#include <cassert>

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>

#define c first
#define v second

using namespace std;

typedef long long int64;
typedef vector< pair<int, int> >::iterator it;

const int oo = 0x3f3f3f3f;
const int MAX_N = 50005;

vector< pair<int, int> > G[MAX_N];
int N, Distance[MAX_N];
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > Heap;

void InitDijkstra(int Source) {
    memset(Distance, oo, sizeof(Distance));
    Heap.push(make_pair(0, Source));
}

void Dijkstra(int Source) {
    InitDijkstra(Source);
    while (!Heap.empty()) {
        int X = Heap.top().v, C = Heap.top().c;
        Heap.pop();
        if (Distance[X] != oo)
            continue;
        Distance[X] = C;
        for (it Y = G[X].begin(); Y != G[X].end(); ++Y)
            if (Distance[Y->v] == oo)
                Heap.push(make_pair(C + Y->c, Y->v));
    }
}

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

void Print() {
    ofstream out("dijkstra.out");
    for (int X = 2; X <= N; ++X) {
        if (Distance[X] == oo)
            Distance[X] = 0;
        out << Distance[X] << " ";
    }
    out << "\n";
    out.close();
}

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