#include <fstream>
#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;

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

const int MAXN = 50005;
int n, m;
vector< pair<int, int> > v[MAXN];
int d[MAXN];
pair<int, int> h[MAXN];
int s;
bool u[MAXN];

inline int parent(int nod) {
    return nod / 2;
}

inline int leftChild(int nod) {
    return nod * 2;
}

inline int rightChild(int nod) {
    return nod * 2 + 1;
}

inline void upHeap(int nod) {
    if (parent(nod) >= 1 && h[parent(nod)].first > h[nod].first) {
        swap(h[parent(nod)], h[nod]);
        nod = parent(nod);
    }
}

inline void downHeap(int nod) {
    int child = 1;
    while (child > 0) {
        child = 0;
        if (leftChild(nod) <= s) {
            if (h[leftChild(nod)].first < h[nod].first) {
                child = leftChild(nod);
            }
        }
        if (rightChild(nod) <= s) {
            if (h[rightChild(nod)].first < h[nod].first) {
                if (child == 0 || h[rightChild(nod)].first < h[leftChild(nod)].first) {
                    child = rightChild(nod);
                }
            }
        }
        if (child != 0) {
            swap(h[child], h[nod]);
            nod = child;
        }
    }
}

inline void afis() {
    for (int i = 1; i <= s; ++i) {
        fout << h[i].first << ' ' << h[i].second << '\n';
    }
    fout << '\n';
}

inline void add(int val, int nod) {
    s++;
    h[s].first = val;
    h[s].second = nod;
    upHeap(s);
    //afis();
}

inline void del(int nod) {
    h[nod] = h[s];
    s--;
    if (parent(nod) >= 1 && h[parent(nod)].first > h[nod].first) {
        upHeap(nod);
    }
    else {
        downHeap(nod);
    }
    //afis();
}

int main() {

    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }

    for (int i = 1; i <= n; ++i) {
        d[i] = INT_MAX;
    }

    d[1] = 0;
    add(0, 1);
    while (s > 0) {
        pair<int, int> k = h[1];
        int cost = k.first;
        int nod = k.second;
        u[nod] = 1;
        del(1);
        for (int i = 0; i < v[nod].size(); ++i) {
            if (u[v[nod][i].first] == 0) {
                if (d[v[nod][i].first] > cost + v[nod][i].second) {
                    d[v[nod][i].first] = cost + v[nod][i].second;
                    add(d[v[nod][i].first], v[nod][i].first);
                }
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (d[i] == INT_MAX) {
            d[i] = 0;
        }
        fout << d[i] << ' ';
    }

    fout.close();
    return 0;
}