#include <iostream>
#include<stdio.h>
#include<fstream.h>

using namespace std;

const int inf=1500000;
struct graf
        {
            int nod,cost;
            graf *urm;
        };

graf *a[100001];
long n,m,d[100001],poz[100001],heap[100001],dim;

void add(int x,int y,int costul)
{
    graf *p=new graf;
    p->nod=y;
    p->cost=costul;
    p->urm=a[x];
    a[x]=p;
}

void citire()
{
    int x,y,c;
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&x,&y,&c);
            add(x,y,c);
        }
}

void initializare()
{
    for(int i=1;i<=n;i++)
        {
            d[i]=inf;
            poz[i]=-1;
        }
}

void schimb(int a,int b)
{
    int aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
}

void upheap(int nod)
{
    int tata;
    while(nod>1)
        {
            tata=nod/2;
            if(d[heap[nod]]<d[heap[tata]])
                {
                    poz[heap[nod]]=tata;
                    poz[heap[tata]]=nod;
                    schimb(nod,tata);
                    nod=tata;
                }
            else break;
        }
}

void downheap(int nod)
{
    int fiu;
    while(nod<=dim)
        {
            if(nod*2<=dim)
                {
                    fiu=nod*2;
                    if((fiu+1<=dim)&&(d[heap[fiu+1]]<d[heap[fiu]]))
                        fiu++;
                }
            else return;
            if(d[heap[fiu]]<d[heap[nod]])
                {
                    poz[heap[nod]]=fiu;
                    poz[heap[fiu]]=nod;
                    schimb(nod,fiu);
                    nod=fiu;
                }
            else return;
        }
}


void dijkstra()
{
    int min;
    dim=1;
    d[1]=0;
    poz[1]=1;
    heap[1]=1;
    while(dim)
        {
            min=heap[1];
            schimb(1,dim);
            poz[heap[1]]=1;
            dim--;
            downheap(1);
            graf *t=a[min];
            while(t)
                {
                    if(d[t->nod]>d[min]+t->cost)
                        {
                            d[t->nod]=d[min]+t->cost;
                            if(poz[t->nod]!=-1)
                                upheap(poz[t->nod]);
                            else
                                {
                                    heap[++dim]=t->nod;
                                    poz[heap[dim]]=dim;
                                    upheap(dim);
                                }
                        }
                     t=t->urm;
                }
        }

}

void afisare()
{

fstream g("dijkstra.out",ios::out);

for(int i=2;i<=n;i++)
        {
            if(d[i]!=inf)
                g<<d[i]<<" ";
            else g<<"0 ";
        }
}

int main()
{
    citire();
    initializare();

    dijkstra();
    afisare();
    return 0;
}