#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define inf 0x3f3f3f3f
#define dim 50001
vector<pair <int,int> >v[dim];
bool viz[dim];
int d[dim],n, m;

struct cmp
{
	bool operator () (const int &a,const int &b)
	{
		return d[a]>d[b];
	}
};

priority_queue <int,vector <int>,cmp> Heap;

void dijkstra(int sursa)
{
	memset(d,inf,sizeof(d));
	d[sursa]=0;
	Heap.push (sursa);
	viz[sursa]=1;
	while (!Heap.empty ())
	{
		int re=Heap.top ();
		Heap.pop(); viz[re]=0;
		
		for(int k=0;k<v[re].size();++k)
			if(d[re]+v[re][k].second<d[v[re][k].first])
			{
				d[v[re][k].first]=d[re]+v[re][k].second;
				
				if (!viz[v[re][k].first])
				{
					Heap.push (v[re][k].first);
					viz[v[re][k].first]=1;
				}
			}	
	}			
	
}
				
	
	

int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	
	int  i;
	fin>>n >>m;
	
	for(i=1;i<=m;++i)
	{
		int x, y, z;
		fin>>x >>y >>z;
		v[x].push_back(make_pair (y,z));
	}
	
	dijkstra(1);
	
	for(i=2;i<=n;++i)
	{
		if(d[i]==inf)
			fout<<"0 ";
		else
		fout<<d[i]<<" ";
	}
	return 0;
}