#include <stdio.h>
#define infinit 999


using namespace std;

struct nod{
    nod *urm;
    int inf;
    int la;
    int cost;
}*a;

int n;
int d[100];
int s[100];
int t[100];
int k;
 int m;

void citire()
{
    scanf("%d",&n);

    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {

        nod *x;
        x = new nod;
        scanf("%d %d %d",&x->inf,&x->la, &x->cost);
        x->urm = a;
        a = x;
    }
    k=1;
}

int verf()
{
    for(int i=1;i<=n;i++)
    {
        if(!s[i] && d[i]!=infinit)
            return 1;
    }
    return 0;
}

void initial()
{
    for(int i=1;i<99;i++)
        d[i]=infinit;
    s[k]=1;
    d[k]=0;
    nod *i;
    i=a;
    for(;i;i=i->urm)
    {
        if(i->inf == 1)
        {
            d[i->la]=i->cost;
            t[i->la]=1;
        }
    }
}

int minim()
{
    int min=9999;
    int v;
    for(int i=1;i<=n;i++)
    {
        if(min>d[i] && !s[i])
        {
            min=d[i];
            v=i;
        }
    }
    return v;
}

int val(int x, int y)
{
    for(nod *i=a;i;i=i->urm)
    {
        if(i->la==y && i->inf==x )
            return i->cost;
    }
    return infinit;
}

void rezolvare()
{
    while(verf())
    {
        int min=minim();
        s[min]=1;
        for(int i=1;i<=n;i++)
        {
            if(s[i]==0)
            {
                int x=d[min]+val(min,i);
                if(d[i]>x)
                {
                    d[i]=x;
                    t[i]=min;
                }
            }
        }
    }

}

void drum(int i)
{
    if(t[i]==0)
    {
        printf("%d",i);
        return;
    }
    drum(t[i]);
    printf(" -> %d",i);
}

void afisare()
{
    for(int i=1;i<=n;i++)
    {
        if(s[i])
        {
            drum(i);
            printf(" cost: %d\n",d[i]);
        }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    initial();
    rezolvare();
    //afisare();
    for(int i=2;i<=n;i++)
        printf("%d ",d[i]);

    return 0;
}