#include<fstream>
#define INF 200000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod {
        int info,cost;
        nod *urm;
        };
nod *prim[50001], *a;

int n,m,d[50001],x,y,c[50001],u,p,ct;

void insert(int x, int y, int c)
{       a=new nod;
        a->info=y;
        a->cost=c;
        a->urm=prim[x];
        prim[x]=a;
}

void bellmanFord()
{       nod *q;
        int i,j,X;
        for(i=1;i<=n;i++) d[i]=INF;
        d[1]=0;
        p=u=1;
        c[p]=1;
        while(p<=u)
        {       X=c[p];
                //for(i=1;i<=n;i++)
                for(q=prim[X];q;q=q->urm)
                        if(d[X]+q->cost<d[q->info])
                        {       d[q->info]=d[X]+q->cost;
                                c[++u]=q->info;
                        }
                p++;
        }

}

void write()
{       int i;
        for(i=2;i<=n;i++)
        {       if(d[i]!=INF)
                        fout<<d[i]<<' ';
                else    fout<<"0 ";
        }
}

int main()
{       int i;
        fin>>n>>m;
        for(i=1;i<=m;i++)
        {       fin>>x>>y>>ct;
                insert(x,y,ct);
        }
        bellmanFord();
        write();
        return 0;
}