#include <fstream>
#include <vector>

using namespace std;

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

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

struct edge
{
	edge(int to2=0,int cost2=0):cost(cost2),to(to2){}
	int to,cost;
};

vector<edge> a[MaxN];
int N,M,D[MaxN],H[MaxN],HP[MaxN],V[MaxN],x,y,cost;

inline int father(int nod)
{
	return (nod>>1);
}

inline int left(int nod)
{
	return (nod<<1);
}

inline int right(int nod)
{
	return (nod<<1)+1;
}

inline void upheap(int nod)
{
	if(nod<=H[0])
	{
		int t=father(nod);
		while(t!=0 && 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 r=right(nod),l=left(nod),t=nod;
	if(r<=H[0])
	{
		if(D[H[r]]<D[H[t]])
		{
			t=r;
		}
	}
	if(l<=H[0])
	{
		if(D[H[l]]<D[H[t]])
		{
			t=l;
		}
	}
	while(t!=nod)
	{
		swap(H[t],H[nod]);
		swap(HP[H[t]],HP[H[nod]]);
		nod=t;
		r=right(nod);
		l=left(nod);
		if(r<=H[0])
		{
			if(D[H[r]]<D[H[t]])
			{
				t=r;
			}
		}
		if(l<=H[0])
		{
			if(D[H[l]]<D[H[t]])
			{
				t=l;
			}
		}
	}
}

inline void delheap(int nod)
{
	swap(H[nod],H[H[0]]);
	swap(HP[H[nod]],HP[H[0]]);
	HP[H[H[0]]]=0;
	H[H[0]]=0;
	--H[0];
	downheap(nod);
}

int main()
{
	fin>>N>>M;
	for(register int i=0;i<M;++i)
	{
		fin>>x>>y>>cost;
		a[x].push_back(edge(y,cost));
	}
	fin.close();
	
	H[0]=N;
	H[1]=HP[1]=1;
	for(register int i=2;i<=N;++i)
	{
		D[i]=INF;
		H[i]=HP[i]=i;
	}
	
	while(H[0]>1)
	{
		int x=H[1];
		V[x]=1;
		delheap(1);
		for(vector<edge>::iterator it=a[x].begin();it!=a[x].end();++it)
		{
			if(V[it->to]==0)
			{
				if(it->cost+D[x]<D[it->to])
				{
					D[it->to]=it->cost+D[x];
					upheap(HP[it->to]);
				}
			}
		}
	}
	
	for(register int i=2;i<=N;++i)
	{
		if(D[i]<INF)
		{
			fout<<D[i]<<" ";
		}
		else
		{
			fout<<"0 ";
		}
	}
	fout<<"\n";
	fout.close();
	return 0;
}