#include<stdio.h>

#define nmax 50001
#define inf 0x3f3f3f

struct nod
{
    int drum,cost;
    nod *urm;
} *l[nmax];

int n,m,sol[nmax],viz[nmax];

void add(nod *&,int,int);
void dijkstra();

int main()
{
    int a,b,c;
    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",&a,&b,&c);
            add(l[a],b,c);
        }
    
    dijkstra();
    
    for(int i=2;i<=n;++i)
        if (sol[i]==inf)
            printf("-1");
        else
            printf("%d ",sol[i]);
    return 0;
}

void add(nod *&inc,int info1,int info2)
{
    nod *p=new nod;
    p->drum=info1;
    p->cost=info2;
    p->urm=inc;
    inc=p;
}

void dijkstra()
{
    for(int i=2;i<=n;++i)
        sol[i]=inf;
        
    for(int j=1;j<=n;j++)
        {
            int pmin,min=inf;
            for(int i=1;i<=n;++i)
                if (sol[i]<min && !viz[i])
                    {
                    pmin=i;
                    min=sol[i];
                    }
                    
            
            viz[pmin]=1;        
            nod *t=l[pmin];
            
            while (t)
            {
                if (sol[t->drum] > sol[pmin]+t->cost )
                    sol[t->drum] = sol[pmin]+t->cost;
                
                t=t->urm;
            }
        }
}