#include <fstream>

#include <vector>

#include <algorithm>


#define INF 0x3f3f3f3f

#define NMAX 50005

using namespace std;

struct muchie
{
    int y ;
    int cost ;
};


vector <muchie> v[NMAX] ;

int d[NMAX] ;

int n,m ;

int poz[NMAX],ct ;

int h[NMAX] ;


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

void add(int p) ;

void schimba(int x,int y) ;

void upheap(int p) ;

void downheap(int p) ;

void sterge(int p) ;



void schimba(int x,int y)
{
    int aux ;
    aux=h[x] ;
    h[x]=h[y] ;
    h[y]=aux ;


    poz[h[x]]=y ;
    poz[h[y]]=x ;
}

void upheap(int p)
{
    while(p>1&&d[h[p/2]]<d[h[p]])
    {
        schimba(p/2,p) ;
        p/=2 ;
    }

}

void downheap(int p)
{
    int left,right,aux ;
    left=2*p ;
    right=2*p+1 ;
    aux=p ;
    if(left<=ct&&d[h[left]]<d[h[aux]])
        aux=left ;
    if(right<=ct&&d[h[right]]<d[h[left]])
        aux=right ;
    if(p!=aux)
    {
        schimba(aux,p) ;
        downheap(aux) ;
    }

}

void sterge(int p)
{
    schimba(p,ct) ;
    ct-- ;
    downheap(p) ;
}

void add(int p)
{
    ct++ ;
    h[ct]=p ;
    poz[p]=ct ;
    upheap(ct) ;

}


void read()
{
    int nod1,nod2,dist ;
    f>>n>>m ;
    for(int i=1;i<=m;i++)
    {
        f>>nod1>>nod2>>dist ;
        v[nod1].push_back((muchie){nod2,dist}) ;
    }

}


void write()
{
    for(int i=2;i<=n;i++)
    {
        if(d[i]==INF)
            g<<"0"<<' ' ;
        else
            g<<d[i]<<' ' ;
    }
}


int dijkstra(int nod)
{

    int i,dist,nod2 ;

    for(i=1;i<=n;i++)
        d[i]=INF ;

    d[nod]=0 ;
    poz[nod]=1 ;
    add(nod) ;

    while(ct!=0)
    {
        nod=h[1] ;
        sterge(1) ;

        for(i=0;i<v[nod].size();i++)
        {

            nod2=v[nod][i].y ;
            dist=v[nod][i].cost ;

            if(d[nod]+dist<d[nod2])
            {
                d[nod2]=d[nod]+dist ;

                if(poz[nod2]==0)
                    add(nod2) ;
                else
                    upheap(poz[nod2]) ;

            }

        }


    }


}




int main()
{
    read() ;
    dijkstra(1) ;
    write() ;


    return 0;
}