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

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

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

class Heap{
    int h[DIM];
    int dim;
public:
    Heap():dim(0){}

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

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

    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;
    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.front();
        visited[x]=true;
        heap.pop();

        temp=graph[x];
        while(temp!=NULL){
            if(!visited[temp->node]){
                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;
}