#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;

vector < pair<int,int> > v[50009];
int dist[50009];
int ok[50009];
int heap[50009],m;

void update(int poz)
{
	int val=dist[poz];
	heap[++m]=poz;
	for (int i=m;((i/2)>0) && (dist[heap[i/2]]>val);i/=2)
		heap[i]=heap[i/2],heap[i/2]=poz;
}

void del()
{
	heap[1]=heap[m--];
	int i=1,aux;
	do
	{
		int stg=heap[i],dr=stg;
		if ((i*2<=m) && (dist[heap[i*2]]<dist[heap[i]]))
			stg=heap[i*2];
		if ((i*2+1<=m) && (dist[heap[i*2+1]]<dist[heap[i]]))
			dr=heap[i*2+1];
	    if ((dist[dr]<=dist[stg]) && (dist[dr]<dist[heap[i]]))
			aux=heap[i],heap[i]=heap[i*2+1],heap[i*2+1]=aux; else
				if ((dist[dr]>dist[stg]) && (dist[stg]<dist[heap[i]]))
					aux=heap[i],heap[i]=heap[i*2],heap[i*2]=aux; else
						break;
	}
	while (i<m);
}


int main()
{
	int n,i,x,y,z;
	
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=2;i<=n;++i) dist[i]=99999999;
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&z);
		v[x].pb(make_pair(y,z));
	}
	m=0;
	vector<pair<int,int> >::iterator it;
	for (it=v[1].begin();it!=v[1].end();++it)
		{dist[(*it).first]=(*it).second;
	     update((*it).first);	
		}
	ok[1]=1;	
	for (i=1;i<n;++i)
	{
		int aux=heap[1];
		ok[aux]=1;		
		while ((m>0) && (ok[heap[1]]))
			del();
		
		for (it=v[aux].begin();it!=v[aux].end();++it)
		{if (dist[(*it).first]>dist[aux]+(*it).second)
			dist[(*it).first]=dist[aux]+(*it).second,update((*it).first);	
		}
		
	}
	for (i=2;i<=n;++i)
		if (dist[i]==99999999) printf("0 "); else
			printf("%d ",dist[i]);
return 0;
}