#include <cstdio>
using namespace std;
FILE *in=fopen("dijkstra.in","r");
FILE *out=fopen("dijkstra.out","w");
struct nod{int dest;int inf;nod *leg;};
nod *a[50001],*pin;
int d[50001],p[50001],w[50001];
int val,x,y,z,tan,last;
int n,m,i,j;


void dow(int k)
{
	int ind=k;

for (int j=0;j<2;j++)
	if (k*2+j<=tan)
		        if (d[w[ind]]>d[ w[k*2+j] ])ind=k*2+j;

if (ind!=k)
{
	p[ w[k] ]=ind;p[ w[ind] ]=k;
	
	int big=w[ind];w[ind]=w[k];w[k]=big;
	
	dow(ind);

}


}

void up(int k)
{
int ind=k/2;

if (d[w[ind]]>d[w[k]])
	
{ p[ w[k] ]=ind; p [ w[ind] ]=k;
  
int big=w[ind];w[ind]=w[k];w[k]=big;
  up(ind);

 }

}

int main()
{fscanf(in,"%ld %ld",&n,&m);

for (i=1;i<=n;i++){a[i]=NULL;d[i]=50000;p[i]=-1;}


for (i=1;i<=m;i++)
{fscanf(in,"%d %d %d",&x,&y,&z);
pin=new(nod);
pin->dest=y;
pin->inf=z;
pin->leg=a[x];
a[x]=pin;
}

///init
p[1]=1;
w[1]=1;
tan=1;
d[1]=0;
///dijkstra
while (tan>0)
{
	
last=w[1];
w[1]=w[tan];

p[w[1]]=1;
tan--;
dow(1);
pin=a[last];

while (pin!=NULL)
{
	 i=pin->dest;
	val=d[last]+pin->inf;

 if (d[i]>val)
	  {d[i]=val;
		 if (p[i]==-1)   {w[++tan]=i;p[i]=tan;up(tan);}
		 else    {up(p[i]);dow(p[i]);}
	  }
pin=pin->leg;	  

	  
	  }//end while


}//end dijkstra






for (i=2;i<=n;i++)
	if (d[i]==50000)fprintf(out,"%c ",'0');
       else fprintf(out,"%d ",d[i]);
	
	fprintf(out,"%s","\n");
fclose(in);fclose(out);
}