#include<fstream>
#include<vector>
#define dmax 50003
#define mult 10000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,cp[dmax];
bool t[dmax];
struct muchie
{	int v;
	int cs;
};
vector<struct muchie>g[dmax];
vector<struct muchie>::iterator it;
void dijkstra()
{	int i,r,bun,min=-1;
	r=n-1;
	while(r)
	{	min=-1;
		for(i=1;i<=n;i++)
			if(!t[i])
			{	if(cp[i]<min || min==-1)
				{	min=cp[i];
					bun=i;
				}	
			}
		t[bun]=1;
		for(it=g[bun].begin();it<g[bun].end();it++)	
			if(!t[it->v])
				if(cp[it->v]>cp[bun]+it->cs)
					cp[it->v]=cp[bun]+it->cs;
		r--;	
	}		
}
int main()
{	int i,a,b,c;
	muchie q;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b>>c;
		q.v=b;
		q.cs=c;
		g[a].push_back(q);
	}
	in.close();
	for(it=g[1].begin();it<g[1].end();it++)
		cp[it->v]=it->cs;
	for(i=1;i<=n;i++)
		if(!cp[i])cp[i]=mult;
	t[1]=1;
	dijkstra();
	for(i=2;i<=n;i++)
	{	if(cp[i]==mult)
			cp[i]=0;
		out<<cp[i]<<" ";
	}	
	out.close();
	return 0;
}