#include <cstdio>
#define nd 50001
#define max 999999999
using namespace std;
struct nod{int val; int cost; nod *urm;}*p[nd];

int main()
{
  nod *aux;
 int d[nd],viz[nd],n,m,i,min,a,b,c,k;
 bool ok;
FILE *f,*g;
f=fopen("dijkstra.in","r");
g=fopen("dijkstra.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=n;i++)
    {
        d[i]=max;
        viz[i]=0;
    }
for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d\n",&a,&b,&c);
        aux=new nod;
        aux->val=b;
        aux->cost=c;
        aux->urm=p[a];
        p[a]=aux;
        if(a==1){d[b]=c;}
    }
viz[1]=1;ok=true;
while(ok==true)
    {
        min=max;
        k=0;
        for(i=1;i<=n;i++)
            {
                if(d[i]<min&&viz[i]==0){min=d[i]; k=i;}
            }
        if(min!=max){aux=p[k];
        viz[k]=1;
        while(aux!=NULL)
            { i=aux->val;
                if(viz[i]==0&&d[i]>d[k]+aux->cost)d[i]=d[k]+aux->cost;
                aux=aux->urm;
            }
        }
        else ok=false;
    }
for(i=2;i<=n;i++)
    {if(d[i]==max)d[i]=0;
    fprintf(g,"%d ",d[i]);
    }
fclose(f);
fclose(g);
return 0;
}