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

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

#define c first
#define v second

using namespace std;

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

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

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

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

void Dijkstra(int Source) {
    InitDijkstra(Source);
    while (!Heap.empty()) {
        Node X = Heap.top(); Heap.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)
                Heap.push(Node(X.c + Y->c, Y->v));
    }
}

void Solve() {
    Dijkstra(1);
}

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(Node(C, Y));
    }
    in.close();
}

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

int main() {
    Read();
    Solve();
    Print();
    return 0;
}