#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int n,m,d[50001];
bool inq[50001];
vector<pair<int,int>> g[50001];
queue<int> q;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main()
{
	int x,y,z;
	fin>>n>>m;
	while(m--)
	{
		fin>>x>>y>>z;
		g[x].push_back(make_pair(y,z));
	}
	for(int i=2;i<=n;++i)
		d[i]=690000000;
	q.push(1);
	inq[1]=1;
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		inq[nod]=0;
		for(size_t i=0;i<g[nod].size();++i)
		{
			int vecin=g[nod][i].first,cost=g[nod][i].second;
			if(d[nod]+cost<d[vecin])
			{
				d[vecin]=d[nod]+cost;
				if(!inq[vecin])
				{
					q.push(vecin);
					inq[vecin]=1;
				}
			}
		}
	}
	for(int i=2;i<=n;++i)
		if(d[i]<690000000)
			fout<<d[i]<<" ";
		else
			fout<<"0 ";
	return 0;
}