#include <iostream>
#include <fstream>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,x,y,c,a[5000][5000],i,j,viz[5000];

void init()
{
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			a[i][j]=-1;
}

void matrice()
{
	for(i=1;i<=m;i++)
	{
		f >> x >> y >> c;
		a[x][y]=c;
	}
}

void afis()
{
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<< "\n";
}

void afisare()
{
	for(i=2;i<=n;i++)
		g << a[1][i] << ' ';
}

int col(int i)
{
	int col=0,min=1001;
	for(j=1;j<=n;j++)
	{
		if(a[j][i]!=-1)
			{
				if(a[j][i]<min)
				{
					col=j;
					min=a[j][i];
				}

			}
	}
	return col;
}

void suma()
{
	int s;
	for(i=2;i<=n;i++)
		{
			s=col(i);
			if(s!=1)
				a[1][i]=a[s][i]+a[1][s];
		}
}

int main()
{
	init();
	matrice();
	suma();
	afisare();
	return 0;

}