#include<stdio.h>
#define DIM 50003
#define INF 0x3f3f3f3f

int n,m;
int best[DIM];
bool visited[DIM];

struct Queue{
    int node;
    int cost;
    Queue* next;
} *graph[DIM];


class Heap{
    unsigned char *exist;
    unsigned short *h;
    unsigned short dim;
public:
    Heap():dim(0){
        h=new unsigned short[DIM];
        exist=new unsigned char[DIM/8+1];
    }
    ~Heap(){
        delete[] h;
    }

    void push(int x);
    void pop();
    int top(){
        return dim ? h[1] : 0;
    }
    bool empty(){
        return dim ? false : true;
    }
    int size(){
        return dim;
    }
};

int i;

void Heap::push(int x){
    int father,son;

    if((1<<(x%8))&exist[x>>3])
        return;
    else{
        son=++dim;
        father=son>>1;
        while(father && best[h[father]]>best[x]){
            h[son]=h[father];
            son=father;
            father>>=1;
        }
        h[son]=x;
    }
}

void Heap::pop(){
    int father=1,son,temp;
    exist[h[1]>>3]|=1<<(h[1]%8);

    h[1]=h[dim--];
    while(father<dim){
        son=father<<1;
        if(son<=dim){
            if(son+1<=dim && best[h[son+1]]<best[h[son]])
                ++son;
            if(best[h[son]]<best[h[father]]){
                temp=h[father];
                h[father]=h[son];
                h[son]=temp;
            }else{
                return;
            }
        }
        father=son;
    }
}

void read_and_initialize(){
    int i;
    int a,b,c;
    Queue *temp;

    scanf("%d %d",&n,&m);
    for(i=0;i<m;++i){
        scanf("%d %d %d",&a,&b,&c);
        temp=new Queue;
        temp->node=b;
        temp->cost=c;
        temp->next=graph[a];
        graph[a]=temp;
    }
    for(i=1;i<=n;i++){
        best[i]=INF;
    }
}

void dijkstra(){
    int x;
    Heap heap;
    Queue *temp;

    heap.push(1);
    best[1]=0;

    while(!heap.empty()){
        x=heap.top();
        heap.pop();

        temp=graph[x];
        while(temp!=NULL){
            if(best[temp->node]>best[x]+temp->cost){
                best[temp->node]=best[x]+temp->cost;
                heap.push(temp->node);
            }
            temp=temp->next;
        }
    }
}

void write_solution(){
    int i;
    for(i=2;i<=n;i++){
        if(best[i]==INF){
            printf("%d ",0);
        }else{
            printf("%d ",best[i]);
        }
    }
    printf("\n");
}

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    read_and_initialize();
    dijkstra();
    write_solution();

    return 0;
}