#include<fstream.h>
#include<vector>
#include<algorithm>

using namespace std; 

struct dij { int ind,cost;};

vector < dij > v[50005];

int m,n,p,poz[51000],h[50100],dist[50100],sw[50100];



void upheap (int k)
{
	while (k>=1 && dist[h[k]]<dist[h[k>>=1]])
	{
		poz[h[k]]=(poz[h[k]]^poz[h[k>>1]])^(poz[h[k>>1]]=poz[h[k]]);
		h[k]=(h[k>>=1]^h[k])^(h[k>>=1]=h[k]);
		k>>=1;
	}
}

int x,y,h1;
void downheap()
{
	x=1,y=p;
	while (x!=y)
	{
		y=x,h1=h[y];
		if (y<<1<=p && dist[h1]>dist[h[x<<1]]) x<<=1;
		if ((y<<1)+1<=p && dist[h1]>dist[h[(y<<1)+1]]) x=(y<<1)+1;
		poz[h[x]]=(poz[h[x]]^poz[h1])^(poz[h1]=poz[h[x]]),h[x]=(h[y]^h[x])^(h[y]=h[x]);
	}
}

void dijkstra () 
{
	
	vector< dij >:: iterator  it,it1,it2;
	
	int inf,c,i;
	
	inf=2000000000;
	for (i=2;i<=n;i++)
		dist[i]=inf;
	dist[i]=0;
	
	h[1]=1;
	poz[1]=1;
	sw[1]=1;
	p=1;
	
	while (p)
	{
		c=dist[h[1]];
		it1=v[h[1]].begin();it2=v[h[1]].end();
		for (it=it1;it<it2;++it)
			if ((c+it->cost)<dist[it->ind])
				if (sw[it->ind]==1)
				{
					dist[it->ind]=c+it->cost;
					upheap(poz[it->ind]);
				}
				else 
				{
					sw[it->ind]=1;
					dist[it->ind]=c+it->cost;
					h[++p]=it->ind;
					upheap(p);
				}
		sw[h[1]]=0;
		h[1]=h[p--];
		poz[h[1]]=1;
		downheap();
	}
}

void afisare()
{
	int i;
	ofstream g("dijkstra.out");
	int inf =2000000000;
	for (i=2;i<=n;++i)
	{
		if (dist[i]==inf)
			dist[i]=0;
		g<<dist[i]<<' ';
	}
	g.close();
}

int main ()
{
	int i,a,b,c;
	dij nod;
	ifstream f("dijkstra.in");
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>a>>b>>c;
		nod.ind=b;nod.cost=c;
		v[a].push_back(nod);
	}
	f.close();
	dijkstra();
	afisare();
	return 0;
}