#include <cstdio>
#define inf 100


using namespace std;

FILE *fin=freopen("dijkstra.in","r",stdin);
FILE *fout=freopen("dijkstra.out","w", stdout);

int n,v,m;

struct nod
{
    nod * urm;
    int n;
    int cost;
}*l[100];

void add(nod *&p, int n, int c)
{
    nod *q=new nod;
    q->n=n;
    q->cost=c;
    q->urm=p;
    p=q;
}

void citire()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d %d %d", &a, &b, &c);
        add(l[a],b,c);
       // add(l[b],a,c);
    }
    v=1;
}

int s[100],d[100],t[100];

int cond()
{
    for(int i=1;i<=n;i++)
        if(s[i]==0)
            return 1;
    return 0;
}

void dinamica()
{
    s[v]=1;
    t[v]=v;
    for(nod *i=l[v];i;i=i->urm){
        d[i->n]=i->cost;
        t[i->n]=v;
    }
    for(int i=1;i<=n;i++)
        if(d[i]==0 && i!=v)
            d[i]=inf;
    while(cond()==1)
    {
        int min=2*inf, vm;
        for(int i=1;i<=n;i++)
        if(s[i]==0 && d[i]<min)
        {
            min=d[i];
            vm=i;
        }
        s[vm]=1;
        for(int i=1;i<=n;i++)
            if(s[i]==0)
            {
                int ck=inf;
                for(nod *j=l[vm];j;j=j->urm)
                    if(j->n==i){
                        ck=j->cost;
                        break;
                    }
                if(d[i]>d[vm]+ck)
                {
                    d[i]=d[vm]+ck;
                    t[i]=vm;
                }
            }
    }
}

void afisare(int x)
{
    if(x!=v){
        afisare(t[x]);
        printf("->");
    }
    printf("%d",x);
}

int main()
{
    citire();
    dinamica();
    for(int i=2;i<=n;i++){
        //afisare(i);
        printf("%d ",d[i]);
    }
    return 0;
}