#include <fstream>
#include <list>
#include <algorithm>
#define INF 690000000
using namespace std;
int n,m,d[50001],pos[50001],heap[50001],nh;
bool inq[50001];
list<pair<int,int>> g[50001];
void hswap(int x,int y)
{
	swap(heap[x],heap[y]);
	swap(pos[heap[x]],pos[heap[y]]);
}
bool cmp(int x,int y)
{
	return d[x]<d[y];
}
void upheap(int x)
{
	int p=(x>>1);
	if (p&&cmp(heap[x],heap[p]))
	{
		hswap(x,p);
		upheap(p);
	}
}
void downheap(int x)
{
	int f=(x<<1);
	f+=(f+1<=nh&&cmp(heap[f+1],heap[f]));
	if (f<=nh&&cmp(heap[f],heap[x]))
	{
		hswap(x,f);
		downheap(f);
	}
}
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main()
{
	int i,x,y,z;
	fin>>n>>m;
	nh=n;
	while(m--)
	{
		fin>>x>>y>>z;
		g[x].push_back(make_pair(y,z));
	}
	for(i=1;i<=n;++i)
	{
		heap[i]=pos[i]=i;
		d[i]=INF;
	}
	d[1]=0;
	for(i=2;i<=n;++i)
	{
		int mn=heap[1];
		hswap(1,nh);
		--nh;
		downheap(1);
		for(list<pair<int,int>>::iterator it=g[mn].begin();it!=g[mn].end();++it)
		{
			int vecin=it->first,cost=it->second;
			if(d[mn]+cost<d[vecin])
			{
				d[vecin]=d[mn]+cost;
				upheap(pos[vecin]);
			}
		}
	}
	for(i=2;i<=n;++i)
		if(d[i]<INF)
			fout<<d[i]<<" ";
		else
			fout<<"0 ";
	return 0;
}