#include<stdlib.h>
#include<fstream>
#include<iostream>
using namespace std;
#define inf 107374
int d[50000],t[50000],v[50000],p[50000],n,m,nr;

struct nod
{
	int info;
	int cost;
	nod *ls;
}; 
nod *ad[100];


void citire()
{
	ifstream in("dijkstra.in");
	int i,a,b,c;
	nod *temp;
	//cout<<"n=";
	in>>n;
	//cout<<"m=";
	in>>m;
	for(i=1;i<=m;i++)
	{
		in>>a;
		in>>b;
		in>>c;
		temp=ad[a];
		ad[a]=new nod;
		ad[a]->info=b;
		ad[a]->cost=c;
		ad[a]->ls=temp;
	}
}

inline void INSERT(int nod)
{
	nr++;
	v[nr]=nod;
	
	int poz=nr;	
	while(d[v[poz/2]]>d[nod]) 
	{
		v[poz]=v[poz/2];
		p[v[poz/2]]=poz;
		poz=poz/2;
	}
	if(poz!=nr) v[poz]=nod;
	p[nod]=poz;
}


inline int EXTRACT()
{
	int nod,fiu,poz;
	
	nod=v[1];
	v[1]=v[nr];
	p[v[nr]]=1;

	nr--;
	
	poz=1;
	do
	{
		fiu=0;
		if(poz*2<=nr) fiu=poz*2;
		if(poz*2+1<=nr)
			if(d[v[fiu]]>d[v[fiu+1]]) 
				fiu=fiu+1;
		if(fiu)
			if(d[v[nr+1]]>d[v[fiu]]) 
			{
				v[poz]=v[fiu];
				p[v[fiu]]=poz;
				poz=fiu;
			}
			else 
			{
				fiu=0;
				v[poz]=v[nr+1];	
				p[v[nr+1]]=poz;
			}
		else
		{
			v[poz]=v[nr+1];
			p[v[nr+1]]=poz;
		}
	} while(fiu);

	return nod;
}

inline void UPDATE(int nod)
{
	int poz=p[nod];	
	while(d[v[poz/2]]>d[nod]) 
	{
		v[poz]=v[poz/2];
		p[v[poz/2]]=poz;
		poz=poz/2;
	}
	if(poz!=nr) v[poz]=nod;
	p[nod]=poz;
}


void dijkstra(int x)
{
	int i,nd;
	for(i=1;i<=n;i++)
	{
		d[i]=inf;
		t[i]=x;
	}
	nod *tmp;
	tmp=ad[x];
	while(tmp)
	{
		d[tmp->info]=tmp->cost;
		tmp=tmp->ls;
	}
	d[x]=0;
	t[x]=0;

	d[0]=-inf;

	for(i=1;i<=n;i++)
		if(i!=x) INSERT(i);


for(int k=1;k<=n-1;k++)
{
	nd=EXTRACT();
	//relaxarea muchiei
	nod *tmp=ad[nd];
	while(tmp)
	{
		if(d[tmp->info]>d[nd]+tmp->cost)
		{
			d[tmp->info]=d[nd]+tmp->cost;
			UPDATE(tmp->info);
			t[tmp->info]=nd;
		}
		tmp=tmp->ls;
	}
}
}
int main()
{
	int i,x;
	citire();
	//cout<<"X=";
	//cin>>x;
	ofstream out("dijkstra.out");
	dijkstra(1);
	//cout<<"\nD: ";
	for(i=2;i<=n;i++) if(d[i]<=1000) out<<d[i]<<" "; else out<<"0 ";
	//cout<<"\nT: "; for(i=1;i<=n;i++) cout<<t[i]<<" ";
	out.close();
	
	return 0;
}