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

#define inf 1000000000

using namespace std;

struct nod { int ind, cost; } ;

vector<nod> v[60000];

int sw[60000],dist[60000],h[60000],poz[60000],n,p;

void downheap ()
{
	int x=p,y=1;
	
	while (x!=y)
	{
		x=y;
		if (2*x<=p && dist[h[x]]>dist[h[2*x]]) y=2*x;
		if (2*x+1<=p && dist[h[y]]>dist[h[2*x+1]]) y=2*x+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 upheap (int p)
{
	int x=p;
	while (x>1 && dist[h[x]]<dist[h[x/2]])
	{
		h[x]=(h[x]^h[x/2])^(h[x/2]=h[x]);
		poz[h[x]]=(poz[h[x/2]]^poz[h[x]])^(poz[h[x/2]]=poz[h[x]]);
		x>>=1;
	}
}

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

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

void citire()
{
	int x,y,c,m,i;
	nod z;
	ifstream f("dijkstra.in");
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		z.ind=y;
		z.cost=c;
		v[x].push_back(z);
	}
}

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