#include <fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod{int x,l;nod *urm;};
nod *p=NULL,*u=NULL;

int n,m,i,a,b,l;
nod *lstp[50001],*lstu[50001];
int cost[50001],ant[50001],k,ok,pr,prr;

int v[50001];
int cd[50001],q1,q2;

void add(int inf,int lg, nod *&prim, nod *&ult)
{
    nod *tmp;
    tmp = new nod;
    tmp->x=inf;
    tmp->l=lg;
    if(prim==NULL) prim=tmp;
    else ult->urm=tmp;
    ult=tmp;
    ult->urm=NULL;
}

void bf(int s)
{
    q1=q2=1;
    cd[q1]=s;
    v[cd[q1]]=1;
    nod *j,*j2;
    int lung;
    while(q1<=q2)
    {
        for(j=lstp[cd[q1]];j;j=j->urm)
        {
            k=j->l+cost[cd[q1]];
            ok=0;
            if(k<cost[j->x]) ok=1;
            if(v[j->x]==0 || ok==1)
            {
                v[j->x]=1;
                if(k<cost[j->x]) {cost[j->x]=k;ant[j->x]=cd[q1];}
                /*if(ok==1)
                {
                    pr=j->x;
                    pr=ant[prr];
                    for(j2=lstp[cd[q1]];j2;j2=j2->urm) if(j2->x==pr) {lung=j2->l;break;}
                    while(cost[prr]-lung<cost[pr] && pr!=-1)
                    {
                        prr=pr;
                        pr=ant[prr];
                    }
                }*/
                cd[++q2]=j->x;
            }
        }
        q1++;
    }
}

int main()
{
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        cost[i]=2000000;
        ant[i]=-1;
    }

    for(i=1;i<=m;i++)
    {
        f>>a>>b>>l;
        add(b,l,lstp[a],lstu[a]);
    }

    cost[1]=0;
    bf(1);

    for(i=2;i<=n;i++) g<<cost[i]<<" ";
    g<<"\n";

    f.close();
    g.close();
    return 0;
}