#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 const unsigned short cs; 
typedef const int cud;

class graph {
    vector<short> edgec[NMAX];
    public:
        vector<short> adjl[NMAX];
        
        void add_edge(cs x, cs y, const int cost)
        {   
            adjl[x].push_back(y);
            edgec[x].push_back(cost);
        };
        unsigned int get_cost_rel(cs x, cs i) const 
        { 
            return edgec[x][i]; 
        };
};

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

void dijkstra::update(cs x, cud 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(cs x, cud v)
{
    if (!B.test(x)) {
        heap[++heapsize] = (he_t){x, v};
        heind[x] = heapsize;
        B.set(x);
    }
    update(x, v);
}

short dijkstra::pop()
{
    short 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--) {
        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()) {
        short c = dl.pop(), n;
        for (size_t i = 0; i != G.adjl[c].size(); ++i) {
            unsigned int aux;
            n = G.adjl[c][i];
            if ((aux = CM[c] + G.get_cost_rel(c, i)) < 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]);

}