#include<fstream>
#define INF 0x3f3f3f
using namespace std;
ofstream out("dijkstra.out");
int a[1400][1400],uz[1400],T[1400],d[1400],n,m;
void citire();
int  dijkstra(int start);
int main()
{
	citire();
	dijkstra(1);
	for(int i=2;i<=n;i++)
		out<<d[i]<<" ";
	return 0;
}
void citire()
{
	ifstream in("dijkstra.in");
	in>>n>>m;
	int i,j,c;
	for(;m;m--)
	{
		in>>i>>j>>c;
		a[i][j]=c;
	}
	for(int i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j&&a[i][j]==0)
				a[i][j]=INF;
}
int dijkstra(int start)
{
	int i,j,k,poz;
	for(i=1;i<=n;i++)
	{
		d[i]=a[start][i];
		T[i]=start;
		uz[i]=0;
	}
	uz[start]=1;
	T[start]=0;
		for(i=1;i<n;i++)
		{
			int minim=INF;
				for(j=1;j<=n;j++)
					if(d[j]<minim&&uz[j]==0)
					{
						minim=d[j];
						poz=j;
					}
					uz[poz]=1;
					for(k=1;k<=n;k++)
						if(d[k]>d[poz]+a[poz][k])
						{
							d[k]=d[poz]+a[poz][k];
							T[k]=poz;
						}
		}
		return 1;
}