using namespace std;
#include<fstream>
#include<vector>
ifstream eu("dijkstra.in");
ofstream tu("dijkstra.out");
#define Nmax 50005
# define oo 1<<30
vector< pair <int , int> > G[Nmax];
int D[Nmax],S[Nmax],N,M,poz[Nmax],Heap[Nmax],Nn;
void read()
{
	eu>>N;
	eu>>M;
	Nn=N;
	int a,b,c;
	for(int i=1;i<=M;i++)
	{
		eu>>a>>b>>c;
		G[a].push_back(make_pair(b,c));
	}
}
void Sift(int X)
{
	int Son=X<<1;
	if(Son+1<=N&&D[Heap[Son+1]]<D[Heap[Son]])
		++Son;
	if(Son<=N&&D[Heap[Son]]<D[Heap[X]])
	{
		swap(Heap[X],Heap[Son]);
		swap(poz[Heap[X]],poz[Heap[Son]]);
		Sift(Son);
	}
}
void Percolate(int X)
{
	int Father=X>>1;
	if(Father>0&&D[Heap[X]]<D[Heap[Father]])
	{
		swap(Heap[X],Heap[Father]);
		swap(poz[Heap[X]],poz[Heap[Father]]);
		Percolate(Father);
	}
}
void solve()
{
	vector< pair <int,int> > :: iterator it;
	for(int i=1;i<=N;i++)
	{
		Heap[i]=i;
		poz[i]=i;
		D[i]=oo;
	}
	D[1]=0;
	for(int i=2;i<=Nn;i++)
	{
		int min=Heap[1];
		swap(Heap[1],Heap[N]);
		swap(poz[Heap[1]],poz[Heap[N]]);
		--N;
		Sift(1);
		for(it=G[min].begin();it!=G[min].end();it++)
		{
			int vecin=it->first, cost=it->second;
			if(D[vecin]>D[min]+cost)
			{
				D[vecin]=D[min]+cost;
				Percolate(poz[vecin]);
			}
		}
	}
}
void print()
{
	for(int i=2;i<=Nn;i++)
		if(D[i]==oo)
			tu<<0<<" ";
		else
		tu<<D[i]<<" ";
}

int main()
{
	read();
	solve();
	print();
	return 0;
}