#include<fstream>
#include<vector>
#include<queue>
#define inf 0x3f3f3f
using namespace std;
struct nod
{
	int y,cost;
};
vector< vector< nod> > mat(50001);
vector<int> dist(50001,inf);
int n,m;
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	for(;m;--m)
	{
		int x,y,cost;
		f>>x>>y>>cost;
		mat[x].push_back( (nod) {y,cost} );
	}
	queue<int> q;
	q.push(1);
	dist[1]=0;
	while(!q.empty())
	{
		int x=q.front();
		for(int i=0;i<mat[x].size();++i)
			if(dist[x]+mat[x][i].cost<dist[mat[x][i].y])
			{
				dist[mat[x][i].y]=dist[x]+mat[x][i].cost;
				q.push(mat[x][i].y);
			}
		q.pop();
	}
	for(int i=2;i<=n;++i)
		if(dist[i]==inf)
			g<<0<<" ";
		else
			g<<dist[i]<<" ";
}