#include<stdio.h>
#include<set>
#include<vector>
#define inf 2000000000
using namespace std;
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");
int n,m,d[50001],sol[50002],x,y,z;
char viz[50002];
vector <pair<int,int> > v[50003];
set <pair<int,int> > t;
set<pair<int,int> >::iterator it;
void dijkstra()
{
	int min=inf;
	int k;
	if(!t.empty())
	{
		it=t.begin();
		min=it->first;
		k=it->second;
		sol[k]=min;
		while(viz[it->second])
		{
			t.erase (it);
			it=t.begin();
		}
	}
	if(min!=inf)
	{
		viz[k]=1;
		for(int i=0;i<v[k].size();++i)
			if(!viz[v[k][i].first])
				if(d[v[k][i].first]>d[k]+v[k][i].second)
				{
					d[v[k][i].first]=d[k]+v[k][i].second;
					t.insert (make_pair(d[v[k][i].first],v[k][i].first));
				}
		dijkstra();
	}
}

int main()
{
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&x,&y,&z);
		v[x].push_back (make_pair(y,z));
	}
	
	for(int i=2;i<=n;++i)
	{
		d[i]=inf;
	}
	t.insert (make_pair(0,1));
	dijkstra();
	
	for(int i=2;i<=n;++i)
		if(sol[i]!=inf)
			fprintf(g,"%d ",sol[i]);
		else
			fprintf(g,"0 ");
	
	fclose(f);
	fclose(g);
	return 0;
}