#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int MAXN = 50005;
const int INF = 1 << 30;

int best[MAXN];//best[i] = costul minim ca sa ajungi de la 1 la i

int heapSize;
int H[MAXN], V[MAXN], poz[MAXN];
bool inHeap[MAXN];
int N, M, a, b, c, it, lung;
vector<pair<int, int> > G[MAXN];
//         <vecin, cost>

inline int father(int node) {
    return node / 2;
}

inline int left_son(int node) {
    return 2 * node;
}

inline int right_son(int node) {
    return 2 * node + 1;
}

void read() {
    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
}

void sift(int K) {
    int son;
    do {
        if (heapSize >= right_son(K)) {
            if (H[left_son(K)] < H[right_son(K)])
                son = left_son(K);
            else
                son = right_son(K);
        }else if (heapSize == left_son(K))
            son = left_son(K);
        else son = 0;
        if (son && H[K] > H[son]) {
            swap(H[K], H[son]);
            swap(V[K], V[son]);
            swap(poz[V[K]], poz[V[son]]);
        }
        K = son;
    }while (son);
}

void percolate(int K) {
    while (K != 1 && H[K] < H[father(K)]) {
        swap(H[K], H[father(K)]);
        swap(V[K], V[father(K)]);
        swap(poz[V[K]], poz[V[father(K)]]);
        K = father(K);
    }
}

void cut(int K) {
    H[K] = H[heapSize];
    V[K] = V[heapSize];
    poz[V[K]] = K;
    heapSize--;
    percolate(K);
    sift(K);
}

void dijkstra() {
    best[1] = 0;
    H[1] = 0;
    V[1] = 1;
    poz[1] = 1;
    heapSize++;
    do {
        int node = V[1];
        inHeap[node] = false;
        cut(1);
        vector<pair<int, int> >::iterator it;
        for (it = G[node].begin(); it != G[node].end(); ++it) {
            if (best[it->first] > best[node] + it->second) {
                best[it->first] = best[node] + it->second;
                if (inHeap[it->first]) {
                    H[poz[it->first]] = best[it->first];
                    percolate(poz[it->first]);
                    sift(poz[it->first]);
                }else {
                    inHeap[it->first] = true;
                    H[++heapSize] = best[it->first];
                    V[heapSize] = it->first;
                    poz[it->first] = heapSize;
                    percolate(heapSize);
                }
            }
        }
    }while (heapSize);
}

void write() {
    for (int i = 2; i <= N; ++i)
        if (best[i] == INF)
            fout << 0 << ' ';
        else
            fout << best[i] << ' ';
    fout << '\n';
}

int main() {
    read();
    for (int i = 0; i <= N; ++i)
        best[i] = INF;
    dijkstra();
    write();
    fin.close();
    fout.close();
    return 0;
}