#include <cstdio>
using namespace std;

FILE *in=fopen("bellmanf.in","r");
FILE *out=fopen("bellmanf.out","w");
struct nod{int dest;
                       int cost;
					    nod *leg;};

long int n,m,i,j,last,val;
nod *a[50000],*p;
int x,y,z,c[50000],k,l,d[50000],mark[50000];


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

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

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

}



for (z=1;z<n;z++)
{k=1;l=0;
c[1]=1;mark[1]=z;
d[1]=0;


	

while (l<=k)
{l++;last=c[l];

p=a[last];
 while (p!=NULL)
 {i=p->dest;
  val=d[last]+p->cost;
  if (val<d[i]){d[i]=val;
					  if (mark[i]!=z){c[++k]=i;mark[i]=z;}
				  }
 p=p->leg;
 }
}


}




for (i=2;i<=n;i++)if (d[i]==100000)fprintf(out,"%c ",'0');
else fprintf(out,"%d ",d[i]);

negativ:fprintf(out,"%d ",-1);
fclose(in);
fclose(out);
return 0;
}