#include<fstream.h>

#define nmax 50100
#define mmax 250010
#define inf 10000000
   
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, a[mmax], st[nmax], dis[nmax], cost[mmax], heap[nmax], poz[nmax], el, nr, x[mmax], y[mmax], pret[mmax];
 
void citire()
{
    int i, sum;

    f>>n>>m;
    for(i=1; i<=m; i++){
        f>>x[i]>>y[i]>>pret[i];
        st[x[i]]++;
    }
    f.close();

    sum=0;
    for(i=1; i<=n+2; i++){
        st[i-1]=sum;
        sum=sum+st[i];
    }

    for(i=1; i<=m; i++){
        a[st[x[i]]]=y[i];
        cost[st[x[i]]]=pret[i];
        st[x[i]]--; 
    }
    f.close();
}

void ridica(int p)
{
    int val=heap[p];
    while( (p>>1) >= 1 && dis[val] < dis[heap[ (p>>1) ]]){
        heap[p]=heap[p>>1];
        poz[heap[p>>1]]=p;
        p>>=1;
    }
    
    heap[p]=val;
    poz[val]=p;
} 

void scufunda(int p)
{
    int fiu, aux;
    
    while( (p<<1) <= nr ){
        fiu=p<<1;
        if( (fiu|1) <= nr && dis[heap[fiu]] > dis[heap[fiu|1]] ) fiu|=1;
        
        if( dis[heap[fiu]] < dis[heap[p]] ){
            aux=fiu;
            fiu=p;
            p=aux;

            aux=heap[fiu];
            heap[fiu]=heap[p];
            heap[p]=aux;

            poz[heap[p]]=p;
            poz[heap[fiu]]=fiu;
       }
            else break;
    }
}
            
void parc(int p)
{
    int i;
    for(i=st[p]+1; i<=st[p+1]; i++) 
        if( dis[a[i]] > dis[p] + cost[i] ){
            dis[a[i]] = dis[p] + cost[i];
            ridica(poz[a[i]]);
        }
}

int main()
{
    citire();

    int i, j;
    
    for(i=2; i<=n; i++){
        dis[i]=inf;
        poz[i]=i;
        heap[i]=i;
    }

    nr=n;
    dis[1]=0; poz[i]=1;
    heap[1]=1;
    for(i=1; i<=n; i++){
        el=heap[1]; 
        heap[1]=heap[nr--];
        scufunda(1);

        parc(el);
    }

    for(i=2; i<=n; i++) if(dis[i]==inf) g<<"0 ";
        else g<<dis[i]<<' ';
    
    g.close();
    return 0;
}