#include <fstream>
#include <iostream>
#include <cstdio>

#include <bitset>
#include <vector>
#include <utility>
#include <algorithm>

#include <assert.h>
#include <string.h>
using namespace std;

const int NMAX = 50001;

typedef unsigned short node_t;
typedef unsigned short cost_t;
typedef const unsigned short cnode; 
typedef const short ccost;

class graph {
    public:
        vector< pair<node_t, cost_t> > adjl[NMAX];
        
        void add_edge(cnode x, cnode y, ccost cost)
        {    
            adjl[x].push_back( make_pair(y, cost) );
        };
};

class dijkstra {
    struct he_t { node_t node; unsigned int cost; } heap[NMAX];
    node_t heind[NMAX];
    node_t heapsize;
    bitset<NMAX> B;
    inline void update(cnode, const unsigned int);
    public:
        dijkstra() {heapsize = 0; memset(heind, 0, NMAX * sizeof(short));}
        void add(node_t, const unsigned int);
        short pop();
        bool empty() {return !heapsize;};
};

void dijkstra::update(cnode x, const unsigned int v)
{
    int p = heind[x];
    heap[p].cost = v;
    while(heap[p].cost < heap[p >> 1].cost) {
        heind[heap[p >> 1].node] = p;
        std::swap(heap[p], heap[p >> 1]);
        p >>= 1;
    }
    heind[x] = p;
}

void dijkstra::add(cnode x, const unsigned int v)
{
    if (!B.test(x)) {
        heap[++heapsize] = (he_t){x, v};
        heind[x] = heapsize;
        B.set(x);
    }
    update(x, v);
}

short dijkstra::pop()
{
    node_t p, q, ret = heap[1].node;
    B.reset(ret);
    heind[heap[1].node] = 0;
    heap[1].node = heap[1].cost = 0; // mostly for debug
    
    if (heapsize == 1) {
        heapsize--;
        return ret;
    }
    else { 
        swap(heap[1], heap[heapsize--]);
        heind[heap[1].node] = 1;
        if (heapsize == 1)
            return ret;
    }

    p = 1; q = 2;
    do {
        q = q + (heap[q].cost > heap[q + 1].cost && heap[q + 1].node);
        heind[heap[q].node] = p;
        swap(heap[q], heap[p]);
    } while ( (q = (p = q) << 1) <= heapsize );
    heind[heap[p].node] = p;
    return ret;
}

void input(int& N, graph& G)
{
    int m;
    ifstream f1("dijkstra.in");
    if (!f1.is_open()) { cout << "idiot!" << endl; return; }
    f1 >> N >> m;
    while(m--) {
        unsigned short a, b; int c;
        f1 >> a >> b >> c;
        G.add_edge(a, b, c);
    }
    f1.close();
}

int main()
{
    int N;
    unsigned int CM[NMAX];
    graph G;
    input(N, G);
    memset(CM, 0xFF, NMAX * sizeof(int));
    
    dijkstra dl;
    dl.add(1, 0.0);
    CM[1] = 0;
    while(!dl.empty()) {
        node_t c = dl.pop(), n;
        vector< pair<node_t, cost_t> >::iterator it;
        for (it = G.adjl[c].begin(); it != G.adjl[c].end(); ++it) {
            unsigned int aux;
            n = (*it).first;
            cost_t dist = (*it).second;
            if ((aux = CM[c] + dist) < CM[n])
                dl.add(n, CM[n] = aux);
        }
    }
    freopen("dijkstra.out", "w", stdout);

    for (int i = 2; i <= N; ++i)
		if (CM[i] == (unsigned int)-1) printf("0 ");
		else printf("%d ", CM[i]);


}