#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int NMAX = 50005,
          MMAX = 250005,
          BMAX = 1 << 16;

struct EDGE {
    int v, w; };

struct NOD {
    int n, w; };

int heap_size;

int dist[NMAX], heap[NMAX], pos[NMAX];
char buck[BMAX];
vector<EDGE> g[NMAX];

inline char nextch(void) {
    static int buff = BMAX;

    if(buff == BMAX) {
        buff = 0;
        fread(buck, 1, BMAX, stdin); }

    return buck[buff++]; }

inline void get(int &arg) {
    char ch;

    do {
        ch = nextch(); }
    while(ch < '0' || ch > '9');
    arg = ch - '0';

    while(true) {
        ch = nextch();
        if(ch < '0' || ch > '9')
            return;
        arg = arg * 10 + ch - '0'; } }

inline void rise(int nod) {
    for(; nod > 1 && dist[heap[nod]] < dist[heap[nod/2]]; nod/=2) {
        swap(heap[nod], heap[nod/2]);
        swap(pos[heap[nod]], pos[heap[nod/2]]); } }

inline void fall(int nod) {
    int tmp;

    while(true) {
        tmp = nod;

        if(2 * nod <= heap_size && dist[heap[tmp]] > dist[heap[2 * nod]]) tmp = 2 * nod;
        if(2 * nod + 1 <= heap_size && dist[heap[tmp]] > dist[heap[2 * nod + 1]]) tmp = 2 * nod + 1;

        swap(heap[tmp], heap[nod]);
        pos[heap[tmp]] = tmp;
        pos[heap[nod]] = nod;

        if(tmp == nod)
            return;

        nod = tmp; } }

void dijkstra(int nod) {
    memset(dist, 0xFF, sizeof(dist));
    memset(pos, 0xFF, sizeof(pos));
    EDGE road;

    heap[++ heap_size] = nod;
    dist[nod] = 0;
    pos[nod] = 1;

    while(heap_size > 0) {
        nod = heap[1];
        pos[heap[1]] = -1;
        pos[heap[heap_size]] = 1;
        swap(heap[1], heap[heap_size --]);
        fall(1);

        for(auto &i: g[nod]) {
            road = {i.v , dist[nod] + i.w};

            if(dist[road.v] == -1) {
                dist[road.v] = road.w;
                heap[++ heap_size] = road.v;
                pos[road.v] = heap_size;
                rise(heap_size); }
            else if(road.w < dist[road.v]){
                dist[road.v] = road.w;
                fall(pos[road.v]);
                rise(pos[road.v]); } } } }

int main(void) {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m, u, v, w;

    get(n), get(m);
    for(int i=1; i<=m; ++i) {
        get(u), get(v), get(w);
        g[u].push_back({v, w}); }

    for(int i=1; i<=n; ++i)
        random_shuffle(g[i].begin(), g[i].end());

    dijkstra(1);

    for(int i=2; i<=n; ++i)
        printf("%d ", (dist[i] != -1) ? dist[i] : 0);
    printf("\n");

    return 0; }