#include <cstdio>
#define t(x)    ((x)/2)
#define fs(x)   ((x)*2)
#define fd(x)   ((x)*2+1)
#define MaxN 50009
#define Inf 20000009

using namespace std;

struct muchie{
    int x,c;
    muchie *urm;
};

muchie *G[MaxN];

int n,m,poz[MaxN],cost[MaxN],heap[MaxN],N;

void add(int x,int y,int cost)
{
    muchie *aux=new muchie;
    aux->x=y; aux->c=cost;
    aux->urm=G[x]; G[x]=aux;
}

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

void initial()
{
    for(int i=2;i<=n;i++)
        poz[i]=-1, cost[i]=Inf;
}

void swap(int x,int y)
{
    int aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;
}

void urca_heap(int nod)
{
    while(nod>1 && cost[heap[nod]]<cost[heap[t(nod)]])
    {
        poz[heap[nod]]=t(nod);
        poz[heap[t(nod)]]=nod;
		swap(nod,t(nod));
        nod=t(nod);
    }
}

void coboara_heap(int nod)
{
    while((fs(nod)<=N && cost[heap[nod]]>cost[heap[fs(nod)]]) || (fd(nod)<=N && cost[heap[nod]]>cost[heap[fd(nod)]]))
        if(fd(nod)<=N)
        {
            if(cost[heap[fs(nod)]]<cost[heap[fd(nod)]])
            {
                poz[heap[nod]]=fs(nod);
                poz[heap[fs(nod)]]=nod;
				swap(nod,fs(nod));
                nod=fs(nod);
            }
            else
            {
                poz[heap[nod]]=fd(nod);
                poz[heap[fd(nod)]]=nod;
				swap(nod,fd(nod));
                nod=fd(nod);
            }
        }
        else
            {
                poz[heap[nod]]=fs(nod);
                poz[heap[fs(nod)]]=nod;
				swap(nod,fs(nod));
                nod=fs(nod);
            }
}

void sol()
{
    int min;
    muchie *aux=new muchie;
    initial();
    heap[++N]=1; poz[1]=1;

    while(N)
    {
        min=heap[1];
        swap(1,N);
        poz[heap[1]]=1; N--;
        coboara_heap(1);

        aux=G[min];
        while(aux)
        {
            if(cost[aux->x]>cost[min]+aux->c)
            {
                cost[aux->x]=cost[min]+aux->c;
                if(poz[aux->x]!=-1)
                    urca_heap(poz[aux->x]);
                else
                {
                    heap[++N]=aux->x;
                    poz[aux->x]=N;
                    urca_heap(N);
                }
            }
            aux=aux->urm;
        }
    }
}

void afis()
{
    int i;
    freopen("dijkstra.out","w",stdout);
    for(i=2;i<=n;i++)
        if(cost[i]==Inf)
            printf("0 ");
        else
            printf("%d ",cost[i]);
}

int main()
{
    cit();
    sol();
    afis();
    return 0;
}