#include <cstdio>
#include <fstream>
#include <limits>
#include <queue>
#include <vector>
#include <utility>

void mainQueue()
{
	//std::ifstream in("dijkstra.in");
	//std::ofstream out("dijkstra.out");

	FILE *file = fopen("dijkstra.in", "r");
	
	int nodeCount, arcCount;
	//in >> nodeCount >> arcCount;
	fscanf(file, "%d %d", &nodeCount, &arcCount);

	std::vector<std::vector<std::pair<int, int> > > nodeMatrix(nodeCount + 1);
	std::queue<int> Q;

	for (int i = 0; i < arcCount; i++)
	{
		int source, destination, length;
		//in >> source >> destination >> length;
		fscanf(file, "%d %d %d", &source, &destination, &length);

		nodeMatrix[source].push_back(std::pair<int, int>(destination, length));
	}

	fclose(file);
	
	std::vector<int> D(nodeCount + 1, std::numeric_limits<int>::max());
	D[1] = 0;
	Q.push(1);

	while (!Q.empty())
	{
		int s = Q.front();

		Q.pop();

		for (std::vector<std::pair<int, int> >::iterator i = nodeMatrix[s].begin(); i != nodeMatrix[s].end(); i++)
		{
			int x = i->first;
			int y = i->second;

			if (D[x] > D[s] + y)
			{
				D[x] = D[s] + y;

				Q.push(x);
			}
		}
	}

	file = fopen("dijkstra.out", "w");

	for (int i = 2, z = 0; i <= nodeCount; ++i)
		fprintf(file, "%d ", &(D[i] == std::numeric_limits<int>::max() ? z : D[i]));

	fclose(file);
}


int main()
{
	mainQueue();
}