#include<stdio.h>
#include<vector>
#define pb push_back
#define mp make_pair
#define inf 500000001

using namespace std;

int main()
{
	int n,m,d[50001],a,b,c,i,j;
	vector < pair<int, pair<int,int> > > muchii;
	pair <int,int> p;
	FILE *f=fopen("dijkstra.in","r");

	fscanf(f,"%i%i",&n,&m);
	for(i=0;i<m;i++)
	{
		fscanf(f,"%i%i%i",&a,&b,&c);
		muchii.push_back(mp(a,mp(b,c)));
	}
	fclose(f);

	d[1]=0;
	for(i=2;i<=n;i++)
		d[i]=inf;
	for(i=0;i<n-1;i++)
	{
		for(j=0;j<m;j++)
		{
			p=muchii[j].second;
			if(d[muchii[j].first]+p.second<d[p.first])
				d[p.first]=d[muchii[j].first]+p.second;
		}
	}
	f=fopen("dijkstra.out","w");
	for(i=2;i<=n;i++)
	{
		if(d[i]==inf)
			d[i]=0;
		fprintf(f,"%i ",d[i]);
	}
	fprintf(f,"%s","\n");
	fclose(f);
	return 0;
}