#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct arb {int nod, cost; }; 

vector <arb> v[50005];

int h[60000],sw[60000],poz[60000],dist[60000],k,n,m;

void urca (int p)
{
	while (p>1 && dist[h[p]] < dist[h[p/2]])
	{
		poz[h[p]]=(poz[h[p]]^poz[h[p/2]])^(poz[h[p/2]]=poz[h[p]]);
		h[p]=(h[p]^h[p/2])^(h[p/2]=h[p]);
	p>>=1;
	}
}

void coboara (int poz1 )
{
	int x,y,aux;
	x=poz1; y=k;	
	while (x!=y)
	{
		y=x;
		if (y*2<=k && dist[h[x]]>dist[h[y*2]]) x=y*2;
		if (y*2+1<=k && dist[h[x]]>dist[h[y*2+1]]) x=y*2+1;
		h[x]=(h[x]^h[y])^(h[y]=h[x]);
		poz[h[x]]=(poz[h[x]]^poz[h[y]])^(poz[h[y]]=poz[h[x]]);
	}
}

void cstheap ()
{
	int i;
	k=0;
	vector <arb> :: iterator it;
	for (it=v[1].begin();it<v[1].end();it++)
	{
		k++; 
		h[k]=it->nod;
		dist[it->nod]=it->cost;
		poz[it->nod]=k;
		urca (k);
		sw[it->nod]=1;
	}
}

void dijkstra ()
{
	int i,vmin;
	vector<arb> :: iterator it;
	dist[1]=0;
	for (i=2;i<=n;i++)
		dist[i]=100000000;
	
	cstheap();
	
	while (k)
	{
	    
		vmin=h[1];sw[vmin]=0; h[1]=h[k--]; poz[h[1]]=1; coboara (1);
		
		
		
		for (it=v[vmin].begin();it<v[vmin].end(); it++)
			if (dist[it->nod]>dist[vmin]+it->cost)
			{
			
				if (sw[it->nod]==1)
				{
					dist[it->nod]=dist[vmin]+it->cost;
					urca (poz[it->nod]);
				}
				else
				{
					sw[it->nod]=1;
					dist[it->nod]=dist[vmin]+it->cost;
					h[++k]=it->nod;
					poz[it->nod]=k;
					urca (k);
				}
			}
	
			
	}
}
void citire ()
{
	arb nou;
	int i,x,y,c;
	FILE *f = fopen ("dijkstra.in","r");
	
	fscanf (f,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(f,"%d%d%d", &x,&y,&c);
		nou.nod=y;nou.cost=c;
		v[x].push_back(nou);
	}
	fclose(f);
}

void afisare()
{
	int i;
	FILE *f=fopen ("dijkstra.out","w");
	for (i=2;i<=n;i++)
		if (dist[i]==100000000) fprintf (f,"%d ",0); else 
		fprintf (f,"%d ",dist[i]);
	fclose(f);
}

int main()
{
	citire ();
	dijkstra ();
	afisare ();
	return 0;
}