#include<stdio.h>
#include<queue>
#include<vector>

using namespace std;

#define Nmax 50005
#define inf 0x3f3f3f3f

int N,M;
int d[Nmax],poz[Nmax],Heap[Nmax],nh;

vector < pair<int,int> > l[Nmax];

void swap(int i,int j)
{
    int aux=Heap[i];
    Heap[i]=Heap[j];
    Heap[j]=aux;

    poz[Heap[i]]=i;
    poz[Heap[j]]=j;
}

void up_heap(int t)
{
    for( ; t>1 ; t/=2)
        if (d[Heap[t]] < d[Heap[t/2]])
            swap(t,t/2);
}

void down_heap(int k)
{
    int fiu=1;
    while(fiu)
        {
        fiu=0;
        if (2*k <= nh)
            {
            fiu=2*k;
            if (2*k+1 <= nh && d[Heap[fiu]] > d[Heap[2*k+1]])
                fiu=2*k+1;
            }
        if (fiu && d[Heap[fiu]] < d[Heap[k]])
            {
            swap(k,fiu);
            k=fiu;
            }
        else
            fiu=0;
        }
}

void dijkstra()
{
    for(int i=1;i<=N;++i)
        {
        d[i]=inf;
        Heap[i]=i;
        poz[i]=i;
        }
    d[1]=0;

    int nod;
    for(nh=N; nh>1 ;)
        {
            nod=Heap[1];
            swap(1,nh);
            nh--;
            down_heap(1);

            for(int i=0; i<(int)l[nod].size() ; ++i)
                if (d[ l[nod][i].first ] > d[nod] + l[nod][i].second)
                    {
                    d[ l[nod][i].first ] = d[nod] + l[nod][i].second;
                    up_heap(poz[ l[nod][i].first ]);
                    }
        }

    for(int i=2;i<=N;++i)
        if (d[i]!=inf)
            printf("%d ",d[i]);
        else
            printf("0 ");
    printf("\n");
}

void cit();

int main()
{
    cit();
    dijkstra();
    return 0;
}

void cit()
{
    int a,b,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
        {
        scanf("%d%d%d",&a,&b,&c);
        l[a].push_back( make_pair(b,c) );
        }
}