#include <stdio.h>
#include <vector>
#define nmax 50001
#define inf 1<<30
using namespace std;
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
struct pereche{
int dir,c;};
int heap[nmax],dist[nmax],poz[nmax];
int n,k;
vector <pereche> lista[nmax];
void swaps(int p1, int p2)
{int aux;
    poz[heap[p1]]=p2;
    poz[heap[p2]]=p1;
    aux=heap[p1];
    heap[p1]=heap[p2];
    heap[p2]=aux;
}
void coboara(int p)
{int pmin=0,ok;
    do
    {ok=0;
        if(p*2<=k&&dist[heap[p*2]]<dist[heap[p]])
            pmin=p*2;

        if(p*2+1<=k&&dist[heap[p*2+1]]<dist[heap[p]]&&dist[heap[p*2+1]]<dist[heap[p*2]])
            pmin=p*2+1;

        if(pmin>0&&dist[heap[pmin]]<dist[heap[p]])
        {swaps(p,pmin);
        p=pmin;
        ok=1;}

    }while(ok);
}
void urca(int p)
{
    while(p>0&&dist[heap[p/2]]>dist[heap[p]])
    {swaps(p,p/2);
    p=p/2;}
}
int main()
{
    long i,j,m,x,el; pereche aux;
    fscanf(f,"%d %d",&n,&m);
    heap[++k]=1;
    poz[k]=1;
    for(i=2;i<=n;i++)
        {dist[i]=inf;
        heap[++k]=i;
        poz[k]=k;}
    for(i=1;i<=m;i++)
        {fscanf(f,"%d %d %d",&x,&aux.dir,&aux.c);
        lista[x].push_back(aux);
        }
    fclose(f);
    while(k)
    {el=heap[1];
    swaps(1,k);
    k--;
    coboara(1);
        for(j=0;j<lista[el].size();j++)
            if(dist[lista[el][j].dir]>lista[el][j].c+dist[el])
                {dist[lista[el][j].dir]=lista[el][j].c+dist[el];
                urca(poz[lista[el][j].dir]);
                }
    }
    for(i=2;i<=n;i++)
    {if(dist[i]==inf)
        dist[i]=0;
        fprintf(g,"%d ",dist[i]);}
    fclose(g);
    return 0;
}