#include <cstdio>
#include <vector>
using namespace std;
int nn,cost[50001],h[50001],poz[50001] ;
struct vert
{
    int nod,cost;
} ad;

vector<vert>v[50001];
vector<vert>::const_iterator in,fi;



void sw(int a, int b)
{
    int aux;
    aux=h[a];
    h[a]=h[b];
    h[b]=aux;
    poz[h[a]]=a;
    poz[h[b]]=b;
}

int sift()
{
    sw(1,nn);
    nn--;
    int son=2,tata=1;
    while(son<=nn)
    {
        if(son<nn&&cost[h[son]]>cost[h[son+1]])son++;
        if(cost[h[tata]]>cost[h[son]])
        {
            sw(tata,son);
            tata=son;
            son*=2;
        }
        else break;
    }
    return h[nn+1];
}
void percolate(int fiu)
{
    int tata=fiu/2;
    while(tata>=1)
    {
        if(cost [h[tata]]>cost[h[fiu]])
        {
            sw(tata,fiu);
            fiu=tata;
            tata/=2;
        }
        else break;
    }
}

int lung=1,pozz=0;
char buff[1000001];
int read()
{
    int x=0;
    while(buff[pozz]<'0'||buff[pozz]>'9')
    {
        if(++pozz==lung){lung=fread(buff,1,1000000,stdin);pozz=0; }
    }
    while(buff[pozz]>='0'&&buff[pozz]<='9')
    { x=x*10+buff[pozz]-'0';
        if(++pozz==lung){lung=fread(buff,1,1000000,stdin);pozz=0; }
    }
    return x;
}



int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int i,j,n,m,a,b,c;
    n=read();
    m=read();

    nn=n;
    for(i=1; i<=m; i++)
    {
        a=read();b=read();c=read();
        ad.cost=c;
        ad.nod=b;
        v[a].push_back(ad);
    }
    for(i=1; i<=n; i++)
    {
        cost[i]=12345678;
        poz[i]=h[i]=i;
    }
    cost[1]=0;
    int ok=1;
    while(nn>=1)
    {

        ok=0;
        a=sift();
        //  in=v[a].begin();fi=v[a].end();
        for(i=0; i<v[a].size(); i++)
        {
            if(v[a][i].cost+cost[a]<cost[v[a][i].nod])
            {
                cost[v[a][i].nod]= v[a][i].cost+cost[a];
                percolate(poz[v[a][i].nod]);
                ok=1;
            }
        }

    }
    for(i=2; i<=n; i++)
    {
        if(cost[i]==12345678)printf("0 ");
        else printf("%d ",cost[i]);
    }

    return 0;
}