#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <set>
using namespace std;


#define N 50176
#define INF 0x3f3f3f3f

int sol[N];
vector <int> graf[N], cost[N];
set<pair<int, int> > t;

//char *buffer, *current;

/*
int fileSize(char *filename)
{
	FILE *file = fopen(filename, "rb");
	if (!file)
		return -1;

	fseek(file, 0, SEEK_END);
	int size = ftell(file);

	fclose(file);
	return size;
}


int get()
{
	while (*current < '0' || '9' < *current)
		current++;

	int n = 0;
	while ('0' <= *current && *current <= '9')
		n = n * 10 + *(current++) - '0';

	return n;
}
*/

int main()
{
	/*
	int size = fileSize("dijkstra.in");
	buffer = (char *)malloc(size);
	current = buffer;

	FILE *file = fopen("dijkstra.in", "rt");
	fread(buffer, 1, size, file);
	fclose(file);
*/
	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);

	int m, n, a, b, c, i;
	scanf("%d%d", &n, &m);
	for (i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		graf[a].push_back(b);
		cost[a].push_back(c);
	}
	//free(buffer);


	memset(sol, 0x3f, (n + 1) * sizeof(int));
	sol[1] = 0;

	t.insert(make_pair(0, 1));
	int val, nod, nod2, sum;
	set< pair<int ,int> >::iterator start;

	while (t.size())
	{
		start = t.begin();
		val = (*start).first;
		nod = (*start).second;
		t.erase(*start);

		for (i = 0; i < (int)graf[nod].size(); i++)
		{
			nod2 = graf[nod][i];
			sum = val + cost[nod][i];

			if (sol[nod2] > sum)
			{
				sol[nod2] = sum;
				t.insert(make_pair(sum, nod2));
			}
		}
	}

	for (int i = 2; i <= n; i++)
		if (sol[i] != INF)
			printf("%d ", sol[i]);
		else
			printf("0 ");
	printf("\n");

	return 0;
}