#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;
}

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;
}

void dijkstra(){
    int cur;
    while((cur = findNearest())>0){
        viz[cur]=true;
        list* p = graf[cur];
        while(p){
            if(dist[p->b] > p->c + dist[cur]) dist[p->b] = p->c + dist[cur];
            p = p->next;
        }
    }
}

int main(){
    FILE *f = fopen("dijkstra.in", "r");
    fscanf(f, "%d %d", &n, &m);
    for(int i=2;i <= n;i++) dist[i] = MAXINT;
    for(int i=0; i<m; i++){
        int a,b,c;
        fscanf(f, "%d %d %d", &a,&b,&c);
        if(a==1) dist[b] = c;
        add(a,b,c);
    }
    fclose(f);

    dijkstra();

    FILE *g = fopen("dijkstra.out", "w");
    for(int i=2;i<=n;i++) fprintf(g, "%d ", dist[i]);
    fclose(g);
    return 0;
}