#include <stdio.h>
#include <vector>

using namespace std;

vector <int> nod_x,nod_y,cost;

int lungimea[50001],i,n,m;
short sem;

int main () 
{	
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	scanf("%d %d",&n,&m);
	int x,y,c;

	for (i=0; i<m; i++) 
	{
		scanf("%d%d%d",&x,&y,&c);
		nod_x.push_back(x);
		nod_y.push_back(y);
		cost.push_back(c);
	}

	for (i=0; i<=n; i++) 
		lungimea[i]=-1; 
	
	lungimea[1]=0;

	while (!sem)
	{
		sem=1;
		for (i=0; i<m; i++)
		{
			if (lungimea[nod_x[i]]>-1 && (lungimea[nod_y[i]]==-1 || lungimea[nod_y[i]] > lungimea[nod_x[i]]+cost[i])) 
			{
				lungimea[nod_y[i]]=lungimea[nod_x[i]]+cost[i];
				sem=0;
			}
		}
	}

	for (i=2; i<=n; i++)
		if (lungimea[i]==-1) 
			// nu exista drum
			printf("0 ");
		else 
			printf("%d ",lungimea[i]);

	return 0;
}