#include <fstream>

using namespace std;

int mat[5000][5000], n, m, cd[5001], dist[5001];

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

void citire()
{
	int x,y;
	in>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n;j++)
			mat[i][j]=-1;
	for(int i=1; i<=n; i++)
	{
		in>>x>>y;
		in>>mat[x][y];
	}

}

void alg()
{
	int p=0,u=0,poz=1,i;
	while(p<=u)
	{
		for(i=2; i<=n; i++)
			if(mat[poz][i]!=-1 && dist[i-1]==0)
			{
				u++;
				cd[u]=i;
				dist[i-1]=dist[poz-1]+mat[poz][i];
			}
		p++;
		poz=cd[p];
	}
}

int main()
{
    citire();
    alg();
    for(int i=1; i<n; i++)
		out<<dist[i]<<' ';
	return 0;
}