#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX 50005
#define INF 0xffffff

vector<pair<int,int> >g[MAX];
struct node{ int x,c; }h[MAX];
int n,m,d[MAX],pos[MAX],k;

void remove(){
    pos[h[1].x]=0;
    h[1]=h[k--];
    int t=1,f=2;
    if(k>2 && h[3].c<h[2].c)f=3;
    while(f<=k && h[f].c<h[t].c)
    {
        swap(h[t],h[f]); //update this child with father
        swap(pos[h[t].x],pos[h[f].x]); //change positions
        t=f; f=2*t;
        if(f+1<=k && h[f+1].c<h[f].c)f++;
    }
}

void update(int c,int x){
    int t,f;
    if(pos[x]==0)
    {
        k++;
        h[k].c=c;
        h[k].x=x;
        f=k;
    } else {
        f=pos[x];
        h[f].c=c;
    }
    t=f/2;
    while(t>0 && h[t].c>h[f].c)
    {
        swap(h[t],h[f]); //update this child with father
        swap(pos[h[t].x],pos[h[f].x]); //change positions
        f=t; t=f/2;
    }
}

void dijkstra(){
    int c,x,y;
    for(int i=2;i<=n;i++)d[i]=INF;
    h[1].x=1; h[1].c=0; k=1; //number of elements in heap
    while(k>0)
    {
        c=h[1].c;
        x=h[1].x; //select best node
        remove(); //remove from heap this node
        for(int i=0;i<g[x].size();i++)
        {
            y=g[x][i].second;
            if(d[y]>c+g[x][i].first)
            {
                d[y]=c+g[x][i].first; //we have best cost
                update(d[y],y); //update in heap this node with changed cost
            }
        }
    }
}



int main(){
    int c,x,y;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&x,&y,&c);
            g[x].push_back(make_pair(c,y));
        }
        dijkstra();
        for(int i=2;i<=n;i++)printf("%d ",d[i]==INF?0:d[i]);
    return 0;
}