#include <stdio.h>
#define NMAX 50001
#define MMAX 250001
#define INFI 0x3f3f3f3f
int *a[NMAX],*c[NMAX],ce[MMAX],v[NMAX],v1[NMAX],d[NMAX],t[NMAX];
int j,i,m,n;
int main(void)
{
freopen("dijkstra.in","r",stdin);
int xx,yy,di;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
	{
	scanf("%d%d%d",&xx,&yy,&di);
	v[xx]++;
	//v[y]++;
	}
fclose(stdin);
for(i=1;i<=n;i++)
	{
	a[i]=new int[v[i]+1];
	c[i]=new int[v[i]+1];
	}
freopen("dijkstra.in","r",stdin);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
	{
	scanf("%d%d%d",&xx,&yy,&di);
	a[xx][v1[xx]+1]=yy;
	c[xx][v1[xx]+1]=di;
	v1[xx]++;
	/*
	a[yy][v1[yy]+1]=xx;
	c[xx][v1[xx]+1]=di;
	v1[yy]++;*/
	}
fclose(stdin);

freopen("dijkstra.out","w",stdout);
                  /*
for(i=1;i<=n;i++)
    {
    for(j=1;j<=v[i];j++)
	   printf("%d ",a[i][j]);
    printf("\n");
    }               */
for(i=1;i<=n;i++)
	d[i]=INFI;
int s=1;
d[s]=0;
t[s]=0;
ce[1]=s;
int p,u,nod;
p=u=1;
while(p<=u)
	{
	nod=ce[p];
	for(i=1;i<=v[nod];i++)
		{
        if(d[a[nod][i]]>d[nod]+c[nod][i])
            {
            u++;
            ce[u]=a[nod][i];
            
            d[a[nod][i]]=d[nod]+c[nod][i];
            t[a[nod][i]]=nod;
            }
		}
	p++;
	}
for(i=2;i<=n;i++)
    {
    if(d[i]==INFI) printf("0 ");
    else printf("%d ",d[i]);
    }
printf("\n");
fclose(stdout);
return 0;
}