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

vector < pair<int,int> > v[50009];
int dist[50009],sol[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,i=i*2+1; else
				if ((dist[dr]>dist[stg]) && (dist[stg]<dist[heap[i]]))
					aux=heap[i],heap[i]=heap[i*2],heap[i*2]=aux,i=i*2; 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=1;heap[1]=1;
	vector<pair<int,int> >::iterator it;
	
	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]>(*it).second)
			{
				dist[(*it).first]=(*it).second;	
				sol[(*it).first]=(*it).second+sol[aux];		
				update((*it).first);
			}
		}
		
	}
	for (i=2;i<=n;++i)
		if (dist[i]==99999999) printf("0 "); else
			printf("%d ",sol[i]);
return 0;
}