using namespace std;
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define pq priority_queue
#define mp make_pair
#define Nmax 50001
#define INF 10000
#define InFile "dijkstra.in"
#define OutFile "dijkstra.out"
#define pair pair<int,int>
struct QueueCompare
{
bool operator () (const pair &a, const pair &b) const
	{
	return a.second>b.second;
	}
};
int main ()
{
	int i,j,n,m,x,y,cost,d[Nmax];
	pq<pair, vector<pair > , QueueCompare> heap;
	vector<int> c[Nmax];
	ifstream f(InFile);
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			c[i][j]=INF;
		d[i]=INF;
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>cost;
		c[x][y]=cost;
	}
	f.close();
	d[1]=0;
	heap.push(mp(1, 0));
	while(!heap.empty())
	{
		cost=heap.top().second , x=heap.top().first;
		heap.pop();
		for(i=2;i<=n;i++)
			if(d[i]>cost+c[x][i])
			{
				d[i]=cost+c[x][i];
				heap.push(mp(i,d[i]));
			}
	}
	ofstream g(OutFile);
	for(i=1;i<=n;i++)
		g<<d[i]<<" ";
	return 0;
}