#include <iostream>
#include <fstream>
using namespace std;
#define NMAX 50002
#define MMAX 250002
const int Inf = 1 << 30 ;

struct graf {
    int nod, cost;
    graf *next ;
};

graf *g[NMAX] ;
int next[NMAX], dis[NMAX], added[NMAX] , el, ve , n ,m;

void Add(int where, int what, int cost) ;
void init();

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n, &m);

    init();

    int a,b,c;
    for ( int i = 0; i < m; i++) {
        scanf("%d %d %d",&a, &b, &c);
        Add(a,b,c);
    }

    graf *q;
    next[ve++]= 1;
    dis[1] = 0;
    added[1]++;
    while (el < ve) {
        int r = next[el++] ;
        q = g[r];
        while (q) {
            if (added[q->nod] == 0) {
                added[q->nod]++;
                next[ve++] = q->nod;
            }
            if (dis[q->nod] > dis[r] + q->cost ) {
                dis[q->nod] = dis[r] + q->cost ;
            }
            q = q->next ;
        }
    }

    for ( int i = 2; i<=n ; i++)
        printf("%d ",dis[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

void init() {
    for (int i = 0; i<= n; i++)  {
        g[i] = NULL ;
        dis[i] = Inf ;
        next[i] = 0 ;
        added[i] = 0;
    }
    el = ve = 0;
}


void Add(int where, int what, int cost) {
    graf *t = new graf;
    t->cost = cost ;
    t->nod  = what ;
    t->next = g[where] ;
    g[where]= t ;
}