#include<iostream.h>
#include<fstream.h>


const int max=500001;
const int inf=1<<28;

struct graf
{
	int nod,cost;
	graf *next;
	
};


graf *a[max];
int n,m,d[max],v[max];




void add(int where, int nod, int cost)
{
	graf *q;
	q=new graf;
	q->nod=nod;
	q->cost=cost;
	q->next=a[where];
	a[where]=q;
	
}

void citire()
{
	ifstream f("dijkstra.in");
		
		int x,y,z;
		f>>n>>m;
		for(int i=1; i<=m;i++)
		{
			f>>x>>y>>z;
			add(x,y,z);
		}
		f.close();
}


void afisare()
{
	for(int i=1; i<=n;i++)
	{
		graf *q=a[i];
		cout<<i<<": ";
		while(q)
		{
			cout<<q->nod<<", ";
			q=q->next;
		}
		cout<<endl;
	}
}




void dijkstra()
{
	for(int i=2;i<=n;i++)
		d[i]=inf;
	
	int min, poz_min;
	
	
	for(int j=1;j<=n;j++)
	{
		
		min=inf;
	for(int i=1;i<=n;i++)
		if(d[i]<min&&v[i]==0)
		{
			min=d[i];
			poz_min=i;
		}
		
		v[poz_min]=1;
		
		graf *t;
		t=a[poz_min];
		
		while ( t )      
		{            
			if ( d[ t->nod ] > d[poz_min] + t->cost ) 
				d[ t->nod ] = d[poz_min] + t->cost;   
			
			t = t->next; 
   
} 

			
		
		
	}
	
	
}




int main()
{
	ofstream g("dijkstra.out");
	citire();
	dijkstra();
	
	for(int i=2;i<=n;i++)
		g<<d[i]<<" ";
	
	
return 0;
}