#include <cstdio>
#define MAXINT 32500
#define MAXN 50000
int n, m;

typedef struct list{
    int b,c;
    list* next;
} list;

list* graf[MAXN+1];

void add(int a, int b, int c){
    list *p = new list;
    p->b = b;
    p->c = c;
    p->next = graf[a];
    graf[a] = p;
    list *q = new list;
    q->b = a;
    q->c = c;
    q->next = graf[b];
    graf[b] = q;
}

int dist[MAXN+1];
bool viz[MAXN+1];

int findNearest(){
    int len = MAXINT, nod = 0;
    for(int i=2;i<=n;i++)
        if(!viz[i] && dist[i]<len){ len = dist[i]; nod = i; }
    return nod;
}

int vecini(int a, int b){
    list *p = graf[a];
    while(p){
        if(p->b == b) return p->c;
        p = p->next;
    }
    return -1;
}

void dijkstra(){
    int cur;
    while(cur = findNearest()){
        for(int i=2; i<=n; i++){
            int d;
            if((d = vecini(cur, i))>-1 && dist[i] > d + dist[cur]) dist[i] = d+dist[cur];
        }
        viz[cur]=true;
    }
}

int main(){
    FILE *f = fopen("dijkstra.in", "r");
    fscanf(f, "%d %d", &n, &m);
    for(int i=0; i<m; i++){
        int a,b,c;
        fscanf(f, "%d %d %d", &a,&b,&c);
        add(a,b,c);
    }
    fclose(f);
    for(int i=2;i <= n;i++){ int d = vecini(1,i); dist[i] = d>-1 ? d:MAXINT; }
    dijkstra();
    FILE *g = fopen("dijkstra.out", "w");
    for(int i=2;i<=n;i++) fprintf(f, "%d ", dist[i]);
    fclose(g);
    return 0;
}