#include<fstream>
#include<vector>
#define NMAX 50002
#define Inf 200000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,x,y,c[300000],j;
int main()
{
	fin>>n>>m;
	vector<int>d(n+1);
	vector<int>A[n+1];
	vector<int>cost[n+1];
	for (i=1;i<=n;i++)
	{
		A[i].reserve(1);
		cost[i].reserve(1);
	}
	for (i=1;i<=n;i++)
		d[i]=Inf;
	d[1]=0;
	for (i=1;i<=m;i++)
	{
		fin>>x>>y>>j;
		cost[x].push_back(j);
		A[x].push_back(y);
		A[x].reserve(A[x].size()+1);
		cost[x].reserve(cost[x].size()+1);
	}
	int ic,sc,z;
	ic=sc=1; c[ic]=1;
		while (ic<=sc)
			{
				z=c[ic];
				for (y=0;y<A[z].size();y++)
					if (d[z]+cost[z][y]<d[A[z][y]])
					{
						d[A[z][y]]=d[z]+cost[z][y];
						c[++sc]=A[z][y];
					}
				ic++;
			}
		for (i=2;i<=n;i++)
			if (d[i]!=Inf)fout<<d[i]<<' ';
			else
				fout<<0<<' ';
fout.close();
return 0;}