#include <fstream>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int nr;
struct
{
	int nod,dist;
} heap[1000000];
void insert_heap(int nod,int dist)
{
	nr++;
	heap[nr].nod=nod;
	heap[nr].dist=dist;
	int poz=nr;
	while(poz>1 && heap[poz].dist<heap[poz/2].dist)
	{
		swap(heap[poz],heap[poz/2]);
		poz/=2;
	}
}
void delete_heap()
{
	swap(heap[nr],heap[1]);
	nr--;
	int poz=1;
	while(poz*2+1<=nr && (heap[poz].dist>heap[poz*2].dist or heap[poz].dist>heap[poz*2+1].dist))
	{
		if(heap[poz*2+1].dist>heap[poz*2].dist)
		{
			swap(heap[poz],heap[2*poz]);
			poz*=2;
		}
		else
		{
			swap(heap[poz],heap[2*poz+1]);
			poz*=2;
			poz++;
		}
	}
	if(2*poz<=nr && heap[poz].dist>heap[poz*2].dist)
	{
		swap(heap[poz],heap[2*poz]);
		poz*=2;
	}
}
int rasp[50001];
vector<pair<int,int> >v[50001];
void dijkstra()
{
	while(nr>0)
	{
		int nod=heap[1].nod;
		int dist=heap[1].dist;
		delete_heap();
		if(dist<rasp[nod])
		{
			rasp[nod]=dist;
			for(int i=0; i<v[nod].size(); i++)
			{
				int dest=v[nod][i].first;
				int d=v[nod][i].second;
				if(dist+d<rasp[dest])
				{
					insert_heap(dest,dist+d);
				}
			}
		}
		else
		{
			continue;
		}
	}
}
int n,m,a,b,d;
int main()
{
	f>>n>>m;
	while(m--)
	{
		f>>a>>b>>d;
		v[a].push_back({b,d});
	}
	for(int i=1; i<=n; i++)
	{
		rasp[i]=1000000009;
	}
	insert_heap(1,0);
	dijkstra();
	for(int i=2; i<=n; i++)
	{
		if(rasp[i]!=1000000009)
		{
			g<<rasp[i]<<" ";
		}
		else
		{
			g<<0<<" ";
		}
	}
	return 0;
}