#include<fstream>
#include<queue>
#include<vector>
#include<bitset>
#define Nmax 50001
#define INF 0x3f3f3f
using namespace std;
int N,M,d[Nmax];
vector< pair<int,int> > G[Nmax];
bitset<Nmax> inQ;
queue<int> Q;
void bellman()
{
	int nod,dest,cost;
	vector< pair<int,int> >::iterator it;
	memset(d,INF,sizeof(d));
	d[1] = 0;
	Q.push(1);
	while(!Q.empty())
	{
		nod = Q.front();
		Q.pop();
		inQ[nod] = 0;
		for(it = G[nod].begin();it!=G[nod].end();++it)
		{
			dest = it->first;
			cost = it->second;
			if(d[dest] > cost + d[nod])
			{
				d[dest] = cost+d[nod];
				if(!inQ[dest])
				{
					inQ[dest] = 1;
					Q.push(dest);
				}
			}
		}
	}
}
int main()
{
	ifstream f("dijkstra.in");
	f>>N>>M;
	int i,x,y,c;
	for(i=1;i<=M;++i)
	{
		f>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
	f.close();
	bellman();
	ofstream g("dijkstra.out");
	for(i=2;i<=N;++i)
	{
		if(d[i] == INF)d[i]=0;
		g<<d[i]<<" ";
	}
	g.close();
	return 0;
}