#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define MAXX 200000

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod
{
    int inf,poz;
    nod *urm;
};

nod *G[50010];
int n,m;

void adaug_stiva(nod *&vf, int b, int c)
{
    nod *p=new nod;
    p->inf=c;
    p->poz=b;
    p->urm=vf;
    vf=p;
}

struct pque
{
    int inf,poz;
};

pque heap[50010];
int l;

void adaug_heap(int x, int y)
{
    heap[++l].inf=x;
    heap[l].poz=y;
    int z=l;
    while(heap[z].inf>heap[z/2].inf)
    {
        pque aux=heap[z];
        heap[z]=heap[z/2];
        heap[z/2]=aux;
        z=z/2;
    }
}

void elimin_heap()
{
    pque aux=heap[l];
    heap[l]=heap[l];
    heap[1]=aux;
    l--;
    int z=1;
    if(z>1)
    while(z <=l && ( heap[z].inf<heap[z*2].inf || heap[z].inf <heap[z*2+1].inf ) )
    {
        if(heap[z*2].inf>heap[z*2+1].inf)
        {
            pque aux=heap[z];
            heap[z]=heap[z*2];
            heap[z*2]=aux;
            z=z*2;
        }
        else
        {
            pque aux=heap[z];
            heap[z]=heap[z*2+1];
            heap[z*2+1]=aux;
            z=z*2+1;
        }
    }
}

int viz[50010],d[50010];

void Dijkstra(int x)
{
    for(int i=1;i<=n;i++)
        d[i]=MAXX;
    d[x]=0;
    viz[x]=1;
    {
        nod *it=G[x];
        while(it != 0)
        {
            d[it->poz]=it->inf;
            adaug_heap(-it->inf,it->poz);
            it=it->urm;
        }
    }
    while(l)
    {
        pque aux= heap[1];
        elimin_heap();
        int pct=aux.poz;
        if(viz[pct]==0)
        {
            viz[pct]=1;
            nod *it=G[pct];
            while(it != 0)
            {
                if(viz[it->poz]==0 && d[it->poz] > d[pct] + it->inf)
                {
                    d[it->poz] = d[pct] + it->inf;
                    adaug_heap(-d[it->poz],it->poz);
                }
                it=it->urm;
            }
        }
    }
    for(int i=2;i<=n;i++)
        {
            if(d[i]==MAXX) g<<"0 ";
            else g<<d[i]<<' ';
        }

}

int main()
{

    f>>n>>m;
    for(int i=1;i<=n;i++)
        {
            G[i]=0;
        }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        adaug_stiva(G[a],b,c);
    }
    Dijkstra(1);
    return 0;
}