#include <fstream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

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

const int inf = 0x3f3f3f3f;

struct nodeCost{
	int to;
	int cost;
	nodeCost()
	{
		cost = inf;
	}
};

int n,m;
vector<nodeCost> node[50001];
auto cmp = [](const nodeCost & left, const nodeCost & right){ return left.cost>right.cost;};
priority_queue<nodeCost,vector<nodeCost>,decltype(cmp)> costs(cmp);

int cost[50001];

int main()
{
	in>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int x,y,c;
		in>>x>>y>>c;
		nodeCost nod;
		nod.cost=c;
		nod.to=y;
		node[x].push_back(nod);
	}
	for(int i = 2;i<=n;i++)
	{
		cost[i]=inf;
	}
	nodeCost nod;
	nod.to=1;
	nod.cost=0;
	costs.push(nod);
	while(!costs.empty())
	{
		nodeCost minn = costs.top();
		costs.pop();
		for(nodeCost nod : node[minn.to])
		{
			nodeCost newCost = minn;
			newCost.cost += nod.cost;
			newCost.to=nod.to;
			if(newCost.cost<cost[nod.to]){
                if(cost[nod.to]==inf)
                {
                    cost[nod.to]=newCost.cost;
                    costs.push(newCost);
                }
                else
                {
                    cost[nod.to]=newCost.cost;
                }
			}
		}
	}

	for(int i = 2;i<=n;i++)
	{
		if(cost[i]==inf)
			out << "0 ";
		else
			out << cost[i] << " ";
	}
	return 0;
}