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

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/2]])
	{
		poz[h[k]]=(poz[h[k]]^poz[h[k/2]])^(poz[h[k/2]]=poz[h[k]]);
		h[k]=(h[k/2]^h[k])^(h[k/2]=h[k]);
		k/=2;
	}
}

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

void dijkstra () 
{
	
	vector< dij >:: iterator  it;
	
	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]];
		for (it=v[h[1]].begin();it<v[h[1]].end();++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");
	for (i=2;i<=n;++i)
	{
		if (dist[i]==2000000000)
			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;
}