#include<stdio.h>
#include<vector>
#define INF 10000001
#define mp make_pair
#define pb push_back
#define Nmx 50005

using namespace std;

int n,m,viz[Nmx],cost[Nmx],Heap[Nmx*2],nr;
struct nod
{
    int first,second;
    nod *urm;
};
nod *G[Nmx];

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


void schimb(int x,int y)
{
    int aux=Heap[x];
    Heap[x]=Heap[y];
    Heap[y]=aux;
}

void in_jos(int k)
{
    while(k*2<=nr)
    {
        int p=k*2;
        if(p+1<=nr&&cost[Heap[p+1]]<cost[Heap[p]])
            ++p;
        if(cost[Heap[p]]>cost[Heap[k]])
            return;
        viz[Heap[p]]=k;
        viz[Heap[k]]=p;
        schimb(p,k);
        k=p;
    }
}


void in_sus(int k)
{
    while(k>1)
    {
        if(cost[Heap[k/2]]<cost[Heap[k]])
            return;
        viz[Heap[k]]=k/2;
        viz[Heap[k/2]]=k;
        schimb(k,k/2);
        k=k/2;
    }
}

void dijkstra()
{
    for(int i=2;i<=n;++i)
    {
        viz[i]=-1;
        cost[i]=INF;
    }
    cost[1]=0;
    Heap[1]=1;
    viz[1]=1;nr=1;
    while(nr)
    {
        int min=Heap[1];
        schimb(1,nr);
        Heap[nr--]=0;
        viz[Heap[1]]=1;
        in_jos(1);
        for(nod *p=G[min];p;p=p->urm)
            if(cost[p->first]>cost[min]+p->second)
            {
                cost[p->first]=cost[min]+p->second;
                if(viz[p->first]==-1)
                {
                    Heap[++nr]=p->first;
                    viz[p->first]=nr;
                    in_sus(nr);
                }
                else in_sus(viz[p->first]);
            }
    }
    for(int i=2;i<=n;++i)
        if(cost[i]==INF)
            printf("0 ");
        else printf("%d ",cost[i]);
}

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

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    return 0;
}