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

#define nNodesMax 50010
#define nEdgesMax 250010
#define INF 300000

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

#define cin f
#define cout g
struct Nod
{
	int vf;
	int cost;
	Nod(int vf, int cost):vf{vf},cost{cost}
	{
	}
};

struct Comp
{
	bool operator()(Nod m1, Nod m2) const
	{
		return m1.cost > m2.cost;
	}
};
int freq[nNodesMax];
int nNodes, nEdges;
int dist[nNodesMax];
vector<Nod> vecini[nNodesMax];

void Dijkstra()
{
	priority_queue<Nod, vector<Nod>, Comp> queue;

	Nod nod = Nod{ 1,0 };
	for (int i = 2; i <= nNodes;i++)
	{
		dist[i] = INF;
	}

	queue.push(nod);
	while(!queue.empty())
	{
		nod = queue.top();
		queue.pop();
		for(auto it : vecini[nod.vf])
		{
			if(dist[nod.vf] + it.cost < dist[it.vf])
			{
				dist[it.vf] = dist[nod.vf] + it.cost;
				queue.push(Nod{ it.vf,dist[it.vf] });
			}
		}
	}
	for (int i = 2; i <= nNodes;i++)
	{
		if(dist[i] != INF)
			cout << dist[i] << ' ';
		else cout << 0 << ' ';
	}
}

int main()
{
	int currentNode, nextNode, cost;
	cin >> nNodes >> nEdges;
	for (int i = 1; i <= nEdges;i++)
	{
		cin >> currentNode >> nextNode >> cost;
		vecini[currentNode].push_back(Nod{ nextNode,cost });
	}
	Dijkstra();
	return 0;
}