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