#include <cstdio>

using namespace std;

struct poz
{
    int nod,cost;
    poz *urm;
}*v[50001];

struct pt_heap
{
    int nod2,cost_t;
}heap[50001];

int heap_nr,d[50001],pozitii[50001],viz[50001];
int INF=(1<<31)-1;

void schimba(pt_heap &a,pt_heap &b)
{
    pt_heap aux=a;
    a=b;
    b=aux;
}

void schimba_p(int &a,int &b)
{
    int aux=a;
    a=b;
    b=aux;
}

void up(int x)
{
    while (x!=1 && heap[x].cost_t<heap[x/2].cost_t)
    {
        schimba_p(pozitii[heap[x].nod2],pozitii[heap[x/2].nod2]);
        schimba(heap[x],heap[x/2]);
        x=x/2;
    }
}

void down(int x)
{
    if (x*2==heap_nr)
    {
        if (heap[x].cost_t>heap[x*2].cost_t)
        {
            schimba_p(pozitii[heap[x].nod2],pozitii[heap[x*2].nod2]);
            schimba(heap[x],heap[x*2]);
        }
    }
    else if (x*2<heap_nr)
    {
        int min1=heap[x*2].cost_t,poz1=x*2;
        if (min1>heap[x*2+1].cost_t)
        {
            min1=heap[x*2+1].cost_t;
            poz1=x*2+1;
        }
        if (min1<heap[x].cost_t)
        {
            schimba_p(pozitii[heap[x].nod2],pozitii[heap[poz1].nod2]);
            schimba(heap[x],heap[poz1]);
            down(poz1);
        }
    }
}

void adauga_muchii(int x)
{
    poz *p;
    p=v[x];
    while (p)
    {
        if (viz[p->nod]==0)
        {
            if (pozitii[p->nod]!=0)
            {
                if (heap[pozitii[p->nod]].cost_t>d[x]+p->cost)
                    heap[pozitii[p->nod]].cost_t=d[x]+p->cost;
            }
            else
            {
                heap_nr++;
                heap[heap_nr].nod2=p->nod;
                heap[heap_nr].cost_t=p->cost+d[x];
                pozitii[p->nod]=heap_nr;
                up(heap_nr);
            }
        }
        p=p->urm;
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m;
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);
        if (a==1)
        {
            heap_nr++;
            heap[heap_nr].nod2=b;
            heap[heap_nr].cost_t=c;
            pozitii[b]=heap_nr;
            up(heap_nr);
        }
        else
        {
            if (v[a]==NULL)
            {
                poz *p;
                p=new poz;
                p->nod=b;
                p->cost=c;
                p->urm=NULL;
                v[a]=p;
            }
            else
            {
                poz *p;
                p=new poz;
                p->nod=b;
                p->cost=c;
                p->urm=v[a];
                v[a]=p;
            }
        }
    }
    for (int i=1;i<=n;i++)
        d[i]=INF;
    viz[1]=1;

    for (int i=1;i<=n-1;i++)
    {
        int y=heap[1].nod2;
        viz[y]=1;
        d[heap[1].nod2]=heap[1].cost_t;
        pozitii[heap[heap_nr].nod2]=1;
        heap[1]=heap[heap_nr];
        heap_nr--;
        down(1);
        adauga_muchii(y);
    }
    for (int i=2;i<=n;i++)
        if (d[i]==INF) printf("0 ");
        else printf("%d ",d[i]);
}