#include <bits/stdc++.h>
using namespace std;
/******************************************/
const int nmax=50069;
vector <pair<int, int> >muchii[nmax];
int n,m;
int heapN,rasp[nmax];
struct heap
{
	int dist;
	int nod;
}heap[4*nmax];

/******************************************/
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
/******************************************/
///---------------------------------------------------
inline void readInput()
{
	f>>n>>m;
	int a,b,c;
	while(m--)
	{
		f>>a>>b>>c;
		muchii[a].push_back({b,c});
	}
}

///---------------------------------------------------
void formare()
{
	for(int i=1;i<=n;i++)
	{
		rasp[i]=-1;
	}
}
///---------------------------------------------------
void update(int nod, int dist)
{
	heapN++;
	heap[heapN].nod=nod;
	heap[heapN].dist=dist;
	int pos=heapN;
	while(pos>1 && heap[pos].dist<heap[pos/2].dist)
	{
		swap(heap[pos], heap[pos/2]);
		pos/=2;
	}
}
///---------------------------------------------------
void sterge()
{
	swap(heap[1], heap[heapN]);
	heapN--;
	int pos=1;
	while(2*pos+1<=heapN && (heap[pos].dist>heap[2*pos].dist || heap[pos].dist>heap[2*pos+1].dist))
	{
		if(heap[pos].dist>heap[2*pos].dist)
		{
			swap(heap[pos], heap[2*pos]);
			pos*=2;
		}
		else
		{
			if(heap[pos].dist>heap[2*pos+1].dist)
			{
				swap(heap[pos], heap[2*pos+1]);
				pos=pos*2+1;
			}
		}
	}
	if(pos*2<=heapN)
	{
		if(heap[pos].dist>heap[2*pos].dist)
		{
			swap(heap[pos], heap[2*pos]);
			pos*=2;
		}
	}
}
///---------------------------------------------------
inline void dijkstra()
{
	update(1,0);
	while(heapN)
	{
		int nod=heap[1].nod;
		int dist=heap[1].dist;
		sterge();
		if(rasp[nod]==-1)
		{
			rasp[nod]=dist;
			for(int i=0;i<muchii[nod].size();i++)
			{
				int vecin=muchii[nod][i].first;
				int dist2=muchii[nod][i].second;
				dist2+=dist;
				if(rasp[vecin]==-1) update(vecin,dist2);
			}
		}
	}
}
///---------------------------------------------------
inline void afisare()
{
	for(int i=1;i<=n;i++)
	{
		if(rasp[i]!=-1) g<<rasp[i]<<" ";
		else g<<"0"<<" ";
	}
}
///---------------------------------------------------
int main()
{
	readInput();
	formare();
	dijkstra();
	afisare();
	return 0;
}