#include <stdio.h>
#include <malloc.h>

#define MAXN 50016
#define INFI 666666

long *a[MAXN];
long *cost[MAXN];
long l[MAXN];
long n,m;

long pi[MAXN];
long di[MAXN];
long surs=1;

long q[MAXN];

void cit()
{
FILE *f;
long su,de,co,i;
f=fopen("dijkstra.in","r");
fscanf(f,"%ld %ld",&n,&m);

for(i=0;i<m;i++)
	{
	fscanf(f,"%ld %*d %*d",&su);
	l[su]++;
	}

for(i=1;i<=n;i++)
	{
	a[i]=malloc(sizeof(long)*l[i]);
	cost[i]=malloc(sizeof(long)*l[i]);
	l[i]=0;
	}

fclose(f);
f=fopen("dijkstra.in","r");
fscanf(f,"%*d %*d");

for(i=1;i<=m;i++)
	{
	fscanf(f,"%ld %ld %ld",&su,&de,&co);
	a[su][l[su]]=de;
	cost[su][l[su]]=co;
        l[su]++;
	}
fclose(f);
}

void tip()
{
long i,j;
for(i=0;i<n;i++)
        {
        for(j=0;j<l[i];j++)
                printf("distanta de la %ld la %ld este %ld\n",i,a[i][j],cost[i][j]);
        }
}

void belford()
{
long i,j,k;

for(i=1;i<=n;++i)
        {
        di[i]=INFI;
        pi[i]=0;
        }
di[1]=0;

for(i=1;i<n;i++)
        {
        for(j=1;j<=n;j++)
                {
                for(k=0;k<=l[j];k++)
                        {
                        if(di[a[j][k]]>di[j]+cost[j][k])
                                {
                                di[a[j][k]]=di[j]+cost[j][k];
                                pi[a[j][k]]=j;
                                }
                        }
                }
        
        }
}

long qu[MAXN],staq=0,endq=0;
long co[MAXN];

void push(long t){qu[endq]=t;endq++;}
long front(){return(qu[staq]);}
void pop(){staq++;}

void belford_v2()
{

long i,j;

for(i=1;i<=n;++i)
        {
        di[i]=INFI;
        pi[i]=0;
        }
        
di[1]=0;

push(1);
        while(staq!=endq)
                {
                i=front();pop();
                co[i]=0;
                for(j=0;j<l[i];j++)
                        {
                        if(di[a[i][j]]>di[i]+cost[i][j])
                                {
                                di[a[i][j]]=di[i]+cost[i][j];
                                if(co[a[i][j]]==0)
                                        {
                                        co[a[i][j]]=1;
                                        push(a[i][j]);
                                        }
                                }
                        }
                }
}

void outff()
{
FILE *f;
long i;
f=fopen("dijkstra.out","w");
for(i=2;i<n;i++)
if(di[i]==INFI)
        fprintf(f,"0 ");
else
        fprintf(f,"%ld ",di[i]);
if(di[i]==INFI)
        fprintf(f,"0");
else
fprintf(f,"%ld\n",di[n]);
fclose(f);
}

int main()
{
cit();
belford_v2();
//tip();
outff();
return 0;
}