#include <cstring>

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

#define c first
#define v second

using namespace std;

typedef pair<int, int> Node;
typedef vector<Node>::iterator it;

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

vector<Node> G[MAX_N];
int N, Distance[MAX_N];
priority_queue< Node, vector<Node>, greater<Node> > H;

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

void Dijkstra(int Source) {
    InitDijkstra(Source);
    while (!H.empty()) {
        Node X = H.top(); H.pop();
        if (Distance[X.v] != oo)
            continue;
        Distance[X.v] = X.c;
        for (it Y = G[X.v].begin(); Y != G[X.v].end(); ++Y)
            if (Distance[Y->v] == oo)
                H.push(Node(X.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 = 1; X <= N; ++X)
        if (Distance[X] == oo)
            Distance[X] = 0;
    for (int X = 2; X <= N; ++X)
        out << Distance[X] << " ";
    out << "\n";
    out.close();
}

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