#include <fstream>
#include <vector>

using namespace std;

const char InFile[]="dijkstra.in";
const char OutFile[]="dijkstra.out";
const int MaxN=50111;
const int INF=1<<30;

struct EdgeTo
{
	EdgeTo(int to=0,int cost=0):to(to),cost(cost){}
	int to,cost;
};

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,x,y,cost,D[MaxN],H[MaxN],HP[MaxN];
vector<EdgeTo> G[MaxN];

inline int Father(const int &nod)
{
	return nod>>1;
}

inline int Left(const int &nod)
{
	return nod<<1;
}

inline int Right(const int &nod)
{
	return (nod<<1)+1;
}

inline void UpHeap(int nod)
{
	int t=Father(nod);
	while(t && D[H[t]]>D[H[nod]])
	{
		swap(H[t],H[nod]);
		swap(HP[H[t]],HP[H[nod]]);
		nod=t;
		t=Father(nod);
	}
}

inline void DownHeap(int nod)
{
	int x=nod;
	int l=Left(nod);
	int r=l+1;
	if(l<=H[0])
	{
		if(D[H[x]]>D[H[l]])
		{
			x=l;
		}
	}
	if(r<=H[0])
	{
		if(D[H[x]]>D[H[r]])
		{
			x=r;
		}
	}
	while(x!=nod)
	{
		swap(H[x],H[nod]);
		swap(HP[H[x]],HP[H[nod]]);
		
		nod=x;
		l=Left(nod);
		r=l+1;
		if(l<=H[0])
		{
			if(D[H[x]]>D[H[l]])
			{
				x=l;
			}
		}
		if(r<=H[0])
		{
			if(D[H[x]]>D[H[r]])
			{
				x=r;
			}
		}
	}
}

inline int Pop()
{
	int val=H[1];
	swap(H[1],H[H[0]]);
	swap(HP[H[1]],HP[H[H[0]]]);
	--H[0];
	DownHeap(1);
	return val;
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y>>cost;
		G[x].push_back(EdgeTo(y,cost));
	}
	fin.close();
	
	H[0]=N;
	for(register int i=1;i<=N;++i)
	{
		D[i]=INF;
		H[i]=i;
		HP[i]=i;
	}
	D[1]=0;
	
	while(H[0])
	{
		int nod=Pop();
		if(D[nod]==INF)
		{
			break;
		}
		for(vector<EdgeTo>::iterator it=G[nod].begin();it!=G[nod].end();++it)
		{
			if(D[it->to]>D[nod]+it->cost)
			{
				D[it->to]=D[nod]+it->cost;
				UpHeap(HP[it->to]);
			}
		}
	}
	
	for(register int i=2;i<=N;++i)
	{
		if(D[i]==INF)
		{
			fout<<"0 ";
		}
		else
		{
			fout<<D[i]<<" ";
		}
	}
	fout.close();
	return 0;
}