#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].reserve(4);
            adjl[x].push_back( make_pair(y, cost) );
        };
};

void input(int& N, graph& G)
{
    int m;
    ifstream f1("dijkstra.in");
    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;
    bool done = false;
    input(N, G);
    memset(CM, 0xFF, NMAX * sizeof(int));
    CM[1] = 0;
    while(!done) {
        done = true;
        for (node_t x = 1; x <= N; ++x)
            if (CM[x] != (unsigned int)-1) {
                vector< pair<node_t, cost_t> >::iterator it;
                for (it = G.adjl[x].begin(); it != G.adjl[x].end(); ++it) {
                    node_t y = it->first;
                    cost_t c = it->second;
                    if (CM[x] + c < CM[y]) {
                        CM[y] = CM[x] + c;
                        done = false;
                    }
                }
            }
    }
    
    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]);
    return 0;
}