#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

ifstream In("dijkstra.in");
ofstream Out("dijkstra.out");
vector<pair<int, int> >* Neighbours;
queue<int> Queue;
int* Dist;
bool* InQueue;
int NodesNo;
int EdgesNo;
const int M_INFINITY = 0x3f3f3f3f;

void alloc()
{
	Neighbours = new vector<pair<int, int> >[NodesNo];
	Dist = new int[NodesNo];
	InQueue = new bool[NodesNo];

	memset(Dist, M_INFINITY, sizeof(int) * NodesNo);
	memset(InQueue, false, sizeof(bool) * NodesNo);
}

void dealloc()
{
	delete[] Neighbours;
	delete[] Dist;
	delete[] InQueue;
}

void readData()
{
	In >> NodesNo >> EdgesNo;
	alloc();

	for (int i = 0, x, y, c; i != EdgesNo; ++i)
	{
		In >> x >> y >> c;
		Neighbours[x - 1].push_back(make_pair(y - 1, c));
	}

	In.close();
}

int getDist(const int& pos)
{
	if (Dist[pos] < M_INFINITY)
		return Dist[pos];

	return 0;
}


void printData()
{
	for (int i = 1; i != NodesNo; ++i)
		Out << getDist(i) << " ";

	Out.close();
}

bool isInQueue(const int& node)
{
	return InQueue[node] == true;
}

void addToQueue(const int& node)
{
	Queue.push(node);
	InQueue[node] = true;
}

int removeFromQueue()
{
	int node = Queue.front();
	Queue.pop();
	InQueue[node] = false;

	return node;
}

void solve()
{
	Dist[0] = 0;
	addToQueue(0);

	while (!Queue.empty())
	{
		int node = removeFromQueue();

		for (auto it = Neighbours[node].begin(); it != Neighbours[node].end(); ++it)
			if (Dist[node] + it->second < Dist[it->first])
			{
				Dist[it->first] = Dist[node] + it->second;

				if (!isInQueue(it->first))
					addToQueue(it->first);
			}
	}
}

int main()
{
	readData();
	solve();
	printData();
	dealloc();

	//system("pause");
	return 0;
}