#include <cstdio>
#define MAXINT 32500
#define MAXN 50003
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;
}

void swap(int &a, int &b){
    int c = a;
    a = b; b = c;
}

bool viz[MAXN];
int dist[MAXN+1];
int heap[MAXN];
int dim = 0;

bool maimic(int p1,int p2){
    if(dist[heap[p1]] < dist[heap[p2]]) return true;
    return false;
}
void upheap(int poz){
    if(poz==1) return;
    int p = poz/2;
    if(maimic(poz,p)){
        swap(heap[poz],heap[p]);
        upheap(p);
    }
}
void downheap(int poz){
    int f1 = poz*2;
    int f2 = poz*2+1;
    int min = poz;
    if(f1<=dim) min = maimic(poz,f1)?poz:f1;
    if(f2<=dim) min = maimic(min,f2)?min:f2;
    if(min!=poz){
        swap(heap[min],heap[poz]);
        downheap(min);
    }
}
int extractMin(){
    int min = heap[1];
    heap[1] = heap[dim];
    dim--;
    downheap(1);
    return min;
}

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

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);
    }
    for(int i=2;i<=n;i++){
        heap[++dim] = i;
        upheap(dim);
    }
    fclose(f);

    dijkstra();

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