#include <fstream>
#include <vector>
#include <utility>
#include <cstring>
#include <cstdlib>
using namespace std;

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

const int MAXN = 250010, INF = 1<<29;

int hn;
int n,m,a,b,c,costuri[MAXN];

struct muchie {
    int first, second;
    inline bool operator<(const muchie other) {
        return first < other.first;
    }
    inline bool operator>(const muchie other) {
        return first > other.first;
    }

};

muchie make_muchie(int a, int b) {
    muchie *ret = (muchie*)malloc(sizeof(muchie));
    ret->first = a;
    ret->second = b;
    return *ret;
}

vector<pair<int, short> > g[MAXN];
muchie h[MAXN];

template<class T>
void push_heap(T val) {
    h[++hn] = val;
    int i = hn;
    while(i > 1 && h[i] < h[i/2]) {
        swap(h[i], h[i/2]);
        i /= 2;
    }
}

template<class T>
T pop_heap() {
    T ret = h[1],a,b;
    swap(h[1], h[hn--]);
    int i = 1;
    while(true) {
        if(2*i > hn)
            break;
        if(2*i+1 > hn) {
            if(h[i] > h[2*i])
                swap(h[i], h[2*i]);
            break;
        } else {
            if(h[i] > h[2*i]) {
                swap(h[i], h[2*i]);
                i *= 2;
            } else if(h[i] > h[2*i+1]) {
                swap(h[i], h[2*i+1]);
                i = 2*i+1;
            } else {
                break;
            }
        }
    }
    return ret;
}

void dijkstra(int nod) {
    push_heap(make_muchie(0, nod));
    muchie tmp;
    int cost, i;
    while(hn) {
        tmp = pop_heap<muchie>();
        nod = tmp.second;
        cost = tmp.first;
        for(i=0; i<g[nod].size(); ++i) {
            if(costuri[g[nod][i].first] > cost + g[nod][i].second) {
                push_heap(make_muchie(cost + g[nod][i].second, g[nod][i].first));
                costuri[g[nod][i].first] = cost + g[nod][i].second;
            }
        }

    }
}

int main() {
    int i;
    in>>n>>m;
    for(i=1; i<=m; i++) {
        in>>a>>b>>c;
        g[a].push_back(make_pair(b, c));
    }
    for(i=1; i<=n; i++) {
        costuri[i] = INF;
    }
    costuri[1] = 0;
    dijkstra(1);
    for(i=2; i<=n; i++) {
        out<<(costuri[i] == INF ? 0 : costuri[i] )<<' ';
    }
    return 0;
}