#include <fstream>
#include <queue>
#include <vector>
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define NMAX 50005
#define INF 0x3f3f3f3f

using namespace std;

ifstream in(IN);
ofstream out(OUT);

int n, m, dmin[NMAX];

vector < pair<int, int> > G[NMAX];

bool viz[NMAX];

queue <int> Q;

int main()
{
	int a, b, c, i, nod;
	in>>n>>m;
	for(i=0; i<m; ++i)
	{
		in>>a>>b>>c;
		G[a].push_back(make_pair(b, c));
	}
	for(i=1; i<=n; ++i)
		dmin[i]=INF;
	Q.push(1);
	dmin[1]=0;
	viz[1]=1;
	while(!Q.empty())
	{
		nod=Q.front();
		Q.pop();
		viz[nod]=0;
		for(i=0; i<G[nod].size(); ++i)
			if(dmin[nod] + G[nod][i].second < dmin[G[nod][i].first])
			{
				dmin[G[nod][i].first] = dmin[nod] + G[nod][i].second;
				if(!viz[G[nod][i].first])
				{
					Q.push(G[nod][i].first);
					viz[ G[nod][i].first ]=1;
				}
			}
	}
	for(i=2; i<=n; ++i)
		if(dmin[i]<INF)
			out<<dmin[i]<<' ';
		else out<<0<<' ';
	out<<'\n';
	in.close();
	out.close();
	return 0;
}