#include<iostream>
using namespace std;

struct nod{
	int nr;
	int dist;
	nod *urm;
};



nod* v[50001];

long distante[50001];

int n,m;

int main(void)
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
int i;

cin>>n>>m;
int a,b,c;

for(i=1; i<=m; i++)
{
	cin>>a>>b>>c;
	
	
	nod *p=new nod;
	p->urm=v[a];

	p->nr=b;
	p->dist=c;
	
	v[a]=p;
	

}
	
	
distante[1]=0;

long max=2000000000;


for(i=2; i<=n; i++)distante[i]=max;


for(i=1; i<=n; i++)
{
	if(v[i])
	{
		nod *r=new nod;
		r=v[i];
		while(r)
		{ if((distante[i]+r->dist)<distante[r->nr])distante[r->nr]=distante[i]+r->dist;
		r=r->urm;

		}
	
	}

	
}
	
for(i=2; i<=n; i++)cout<<distante[i]<<" ";	
	
	return 0;
}