#include <fstream>
#include <queue>
#include <climits>

#define MAX_DIM_TREE 262150 // 2^18 - 1
#define MAX_DIM_VECT 100010
using namespace std;

typedef struct node
{
	int identifier;
	int arcLength;
	struct node *next;
}Node;

typedef struct QueueElem
{
	int identifier;
	int pathLength;
}QueueElem;

void ReadData(int m, Node** adjencyList, istream& fin);
void Dijkstra(int startId, Node** adjencyList, int* pathList, bool* flagList);
void WriteResult(int n, int* pathList, ostream &fout);

int main()
{
	ifstream fin;
	ofstream fout;
	fout.open("dijkstra.out");
	fin.open("dijkstra.in");

	int n, m;
	fin >> n >> m;

	Node** adjencyList = new Node*[n + 1]();
	int* pathList = new int[n + 1]();
	for(int i = 1; i <= n; i++)
	{
		pathList[i] = INT_MAX;
	}
	bool* flagList = new bool[n + 1]();

	ReadData(m, adjencyList, fin);

	Dijkstra(1, adjencyList, pathList, flagList);

	WriteResult(n, pathList, fout);

	fin.close();
	fout.close();
	return 0;
}

void ReadData(int m, Node** adjencyList, istream& fin)
{
	int start, end, cost;
	for(int i = 0; i < m; i++)
	{
		fin >> start >> end >> cost;

		Node* newNode = new Node();
		newNode->identifier = end;
		newNode->arcLength = cost;
		newNode->next = adjencyList[start];
		adjencyList[start] = newNode;
	}
}

void Dijkstra(int startId, Node** adjencyList, int* pathList, bool* flagList)
{
	QueueElem* start = new QueueElem();
	start->identifier = startId;
	start->pathLength = 0;

	auto cmp = [](QueueElem* n1, QueueElem* n2) { return n1->pathLength > n2->pathLength ;};
	std::priority_queue<QueueElem*, std::vector<QueueElem*>, decltype(cmp)> queue(cmp);

	pathList[1] = 0;
	queue.push(start);

	while(!queue.empty())
	{
		QueueElem* top = queue.top();
		queue.pop();

		if(flagList[top->identifier] == false)
		{
			flagList[top->identifier] = true;

			Node* current = adjencyList[top->identifier];

			while(current != NULL)
			{
				if(pathList[current->identifier] > (pathList[top->identifier] + current->arcLength))
				{
					pathList[current->identifier] = pathList[top->identifier] + current->arcLength;

					QueueElem* newElem = new QueueElem();
					newElem->identifier = current->identifier;
					newElem->pathLength = pathList[current->identifier];
					queue.push(newElem);
				}

				current = current->next;
			}
		}
	}
}

void WriteResult(int n, int* pathList, ostream &fout)
{
	for(int i = 2; i <= n; i++)
	{
		if(pathList[i] == INT_MAX)
		{
			fout << 0 << " ";
		}
		else
		{
			fout << pathList[i] << " ";
		}
	}
}