#include<cstdio>
#include<fstream>
#include<vector>  
#define MAX_N 50010
#define oo 1<<20
using namespace std;
int n,m,a,b,c,i,j,d[MAX_N],u[MAX_N],H[MAX_N],k;
vector<pair<int,int> > V[MAX_N]; 
void read(),dijkstra_heap(),show(),swap(int,int),heapup(int),heapdown(int);
ifstream in("dijkstra.in");ofstream out("dijkstra.out");
int main()
{
	read();
	dijkstra_heap();
	show();
	return 0;
}
void read()
{
	//freopen("dijkstra.in","r",stdin);
	//freopen("dijkstra.out","w",stdout);
	in>>n>>m;//scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		in>>a>>b>>c,V[a].push_back(make_pair(b,c));//scanf("%d%d%d",&a,&b,&c),
}
void dijkstra_heap()
{
	int pmin;
	vector<pair<int,int> >::iterator it;
	for(i=2;i<=n;i++)d[i]=oo,u[i]=-1;//initializam & selectam primul nod
	 
	u[1]=1;	H[++k]=1;
	for(;k;)
	{
		pmin=H[1];swap(1,k);k--;//extragem cel mai mic cost
		u[H[1]]=1;//vizitam
		heapdown(1);
		//relaxeaza graful
		for(it=V[pmin].begin();it!=V[pmin].end();it++)
		{			
			if(d[it->first] > d[pmin]+it->second) 
				d[it->first] = d[pmin]+it->second;
			if(u[it->first] != -1)
				heapup(u[it->first]);
			else
			{
				H[++k]=it->first;
				u[H[k]]=k;
				heapup(k);				
			}
		}
	}
}
void heapup(int node)
{
	int dad;
	for(;node>1;)
	{
		dad = node>>1;
		if(d[H[node]]<d[H[dad]])
		{
			u[H[node]] = dad;
			u[H[dad]]  = node;			
			swap(dad,node);
			node = dad;
		}
		else 
			break;
	}
}
void heapdown(int node)
{
	int child;
	while(node <= k)
	{
		child = node;
		if((node<<1) <= k)
		{
			child = node<<1;
			if(child+1<=k && d[H[child+1]]<d[H[child]])
				child++;
		}
		else
			break;
		if(d[H[child]]<d[H[node]])
		{
			u[H[node]]=child;
			u[H[child]]=node;
			swap(child,node);
			node = child;
		}
		else
			break;
	}
}
void swap(int x,int y)
{
	int aux;
	aux =H[x];
	H[x]=H[y];
	H[y]=aux;
}
void show()
{
	for(i=2;i<=n;i++)
		out<<(d[i]==oo?0:d[i])<<" ";//printf("%d ",(d[i]==oo?0:d[i]));
}