#include <fstream>
using namespace std;

int a[5001][5001], n, m, cd[10001], dist[5001], i, j;

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

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

void preluc()
{
	int p=0, u=0, acum=1;
	while(p<=u)
	{
		for(i=2; i<=n; i++)
			if(a[acum][i]!=-1 && (dist[i]==0 || dist[acum]+a[acum][i]]<dist[i]))
			{
				u++;
				cd[u]=i;
				dist[u]=dist[acum]+a[acum][i];
			}
		p++;
		acum=cd[p];
	}
	for(i=2; i<=n; i++)
		cout<<dist[i]<<' ';
}

int main()
{
    citire();
    preluc();
    return 0;
}