#include<fstream>
using namespace std;

#define N 50001
#define M 250001

const int Inf=(1<<29);

int n,m;
int h[N],l,d[N],poz[N];
int start[N],g[M][3];

void read()
{
	int i,j,k;
	ifstream fin("dijkstra.in");
	fin>>n>>m;
	while(m)
	{
		fin>>i>>j>>k;
		g[m][0]=start[i];
		g[m][1]=j;
		g[m][2]=k;
		start[i]=m--;
	}
}

void up(int j)
{
	int i;
	while(j>1)
	{
		i=j/2;
		if(d[h[i]]>d[h[j]])
		{
			h[i]+=h[j];
			h[j]=h[i]-h[j];
			h[i]-=h[j];
			poz[h[i]]=i;
			poz[h[j]]=j;
			j=i;
		}
		else j=1;
	}
}

void down(int j)
{
	int i,max=n/2;
	while(j<=max)
	{
		i=2*j;
		if(i<n&&d[h[i+1]]<d[h[i]]) i++;
		if(d[h[i]]<d[h[j]])
		{
			h[i]+=h[j];
			h[j]=h[i]-h[j];
			h[i]-=h[j];
			poz[h[i]]=i;
			poz[h[j]]=j;
			j=i;
		}
		else j=max+1;
	}
}

void dijkstra()
{
	int nod,i,j,k;
	poz[h[++l]=1]=1;
	for(i=2;i<=n;i++) d[i]=Inf;
	for(k=1;k<n;k++)
	{
		nod=h[1];
		h[1]=h[l--];
		down(1);
		for(i=start[nod];i;i=g[i][0])
			if(d[g[i][1]]>d[nod]+g[i][2])
			{
				d[g[i][1]]=d[nod]+g[i][2];
				if(!poz[g[i][1]])
				{
					poz[h[++l]=g[i][1]]=l;
					up(l);
				}
				else	up(poz[g[i][1]]);
			}
	}
}

void write()
{
	ofstream fout("dijkstra.out");
	for(int i=2;i<=n;i++)
		if(d[i]==Inf) fout<<"0 ";
		else fout<<d[i]<<' ';
	fout<<"\n";
}

int main()
{
	read();
	dijkstra();
	write();
	return 0;
}