# include <cstdio>
# include <vector>
# include <queue>
using namespace std;

vector <int> muchie[50001], costm[50001];
queue <int> coada;
int n, m, a, b, c, nod, nodnou;
int costf[50001];
char fr[50001];

int main ()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d%d%d", &a, &b, &c);
		muchie[a].push_back(b);
		costm[a].push_back(c);
	}
	
	for (int i = 1; i <= n; i++)
		costf[i] = -1;
	coada.push (1);
	costf[1] = 0;
	fr[1] = 1;
	
	while (coada.size())
	{
		nod = coada.front();
		for (int i = 0; i < muchie[nod].size(); i++)
		{
			nodnou = muchie[nod][i];
			if ( costf[nodnou] == -1 || (costf[nodnou] > (costf[nod] + costm[nod][i]) ))
				if (fr[nodnou] == 0)
				{
					coada.push (nodnou);
					fr[nodnou] = 1;
					costf[nodnou] = costf[nod] + costm[nod][i];
				}
				else
					costf[nodnou] = costf[nod] + costm[nod][i];
		}
		coada.pop();
		fr[nod] = 0;
	}
	
	for (int i = 2; i <= n; i++)
		if (costf[i] != -1)
			printf ("%d ", costf[i]);
		else
			printf("0 ");
	
	return 0;
}