#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.2","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.2","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 pred()
{
long i;
for(i=1;i<=n;i++)
        {
        pi[i]=0;
        di[i]=INFI;
        }
di[surs]=0;
}

void dijkstra()
{
long min,pmin,i,j;

for(i=1;i<=n;++i)
        {
        min=INFI;
        for(j=1;j<=n;j++)
        if((di[j]<min)&&(!q[j]))
        {min=di[j];pmin=j;}
        q[pmin]=1;
        for(j=0;j<l[pmin];j++)
                {
                if(di[a[pmin][j]]>di[pmin]+cost[pmin][j])
                        {
                        di[a[pmin][j]]=di[pmin]+cost[pmin][j];
                        pi[a[pmin][j]]=pmin;
                        }
                }
        }
}

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

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