#include<cstdio>
#include<vector>
#define mn -1
using namespace std;
vector<pair<int,int> >a[50001];
int n,m,smin,k,i,j,x,y,c,sum[50001],viz[50001],t[50001];
bool ok;

void citire()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&c);
		a[x].push_back(make_pair(y,c));
	}
}

void form()
{
	for (i=1;i<=n;i++){
		sum[i]=mn;
		t[i]=1;
	}
	sum[1]=0;
	k=1;
	ok=true;

	for(i=0;i<a[1].size();i++){
		x=a[1][i].first;
		c=a[1][i].second;
		sum[x]=c;
	}
}

void dijkstra()
{
	form();
	while (ok==true){
		smin=99999;viz[k]=1;
		for(i=1;i<=n;i++)
			if(sum[i]<smin && viz[i]==0 && sum[i]>=0){
				smin=sum[i];
				k=i;
			}
		if (smin!=99999){
			for(i=0;i<a[k].size();i++){
				y=a[k][i].first;
				c=a[k][i].second;
				if(sum[y]>smin+c || sum[y]==-1){
					sum[y]=smin+c;
					t[y]=k;
				}
			}
		}
		else ok=false;
	}
}

void afisare()
{
	for(i=2;i<=n;i++)
		if(sum[i]==mn)printf("0 ");
	    else printf("%d ",sum[i]);
}

int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
}