#include<stdio.h>
#include<string.h>
#define inf 15000
#define nn 50001
#define mm 250001

int n,m,xp,prec[nn],d[nn],c[mm][mm],s[nn],a[nn],w,q;

void citire()
{
freopen("dijkstra.in","r",stdin);
scanf("%d%d", &n, &m);
int i,x,y,z;
for (i=1; i<=n; i++)
    for (int j=1; j<=n; j++)
	c[i][j]=inf;
for (i=1; i<=n; i++)
    c[i][i]=0;
for (i=1; i<=m; i++)
    {
    scanf("%d%d%d", &x, &y, &z);
    c[x][y]=z;
    }
//scanf("%d",&xp);
xp=1;
fclose(stdin);
}

void drum(int w)
{
if (w!=0)
   {
   drum(prec[w]);
   printf("%d ",w);
   }
   else printf("\n");
}

void afisare()
{
freopen("dijkstra.out","w",stdout);
for (int i=2; i<=n; i++)
	if (d[i]==inf)
		//printf("Nu exista drum de la %d la %d\n",xp,i);
		printf("0 ");
	else
	{
//		printf("Lungimea drumului de la %d la %d este %d\n",xp,i,d[i]);
		printf("%d ",d[i]);
//		printf("Drum munim de la %d la %d\n",xp,i);
//		drum(i);
//		printf("\n");
	    }
fclose(stdout);
}

void construire(int n)
{
	int aux;
	for (int i=n/2; i>=1; i--)
	{
		w=i;
		q=0;
		while (q!=w && 2*w<=n)
		{
			q=w;
			if (2*w+1<=n && a[2*w]>a[w*2+1])
			{
				if (a[w]>a[2*w+1])
				{
					aux=a[w];
					a[w]=a[2*w+1];
					a[w*2+1]=aux;
					w=w*2+1;
				}
			}
			else
				if (a[w]>a[2*w])
				{
					aux=a[w];
					a[w]=a[2*w];
					a[w*2]=aux;
					w*=2;
				}
		}
	}
}

int extragere()
{
//	p[++p[0]]=a[1];
	int aux;
//	for (int i=1; i<n; i++)
//	{
		aux=a[1];
		a[1]=a[m--];
		a[m+1]=aux;
		construire(m);
//		p[++p[0]]=a[1];
		if (s[a[1]]!=0)
		   extragere();
		return a[1];
//	}
}


void min(int &k)
{
/*int m=2*inf;
for (int i=1; i<=n; i++)
    if (s[i]==0 && d[i]<m)
       {
       m=d[i];
       k=i;
       }*/

k=extragere();

}

void dijkstra()
{
for (int i=1; i<=n; i++)
    {
    d[i]=c[xp][i];
    s[i]=0;
    if (c[xp][i]<inf)
       prec[i]=xp;
       else prec[i]=0;
    }
s[xp]=1;
prec[xp]=0;
int g=1;
int x=0,k;
while (g==1)
      {
      min(k);
      ++x;
      if (d[k]==inf || x==n)
	 g=0;
	 else
	     {
	     s[k]=1;
	     for (int j=1; j<=n; j++)
		 if (s[j]==0 && d[j]>d[k]+c[k][j])
		    {
		    d[j]=d[k]+c[k][j];
		    prec[j]=k;
		    }
	     }
      }
}

int main()
{
citire();
for (int i=1; i<=n; i++)
	a[i]=i;
m=n;
construire(n);
dijkstra();
afisare();
return 0;
}