#include <fstream>
#include <vector>
#include <set>

using namespace std;

#define INF 1000000000
#define MAXN 50100

class Dijkstra
{
private:
	int nrNoduri, nrMuchii;
	vector<int> vecini[MAXN], cost[MAXN];
	int drum[MAXN];
	set<pair<int,int>> T;

public:
	Dijkstra();
	void Solve();
	void Output();
};

Dijkstra::Dijkstra()
{
	ifstream IN("dijkstra.in");

	IN >> nrNoduri >> nrMuchii;

	for (int i = 1; i <= nrMuchii; i++)
	{
		int x,y,z; IN >> x >> y >> z;
		vecini[x].push_back(y);
		cost[x].push_back(z);
	}

	IN.close();
}

void Dijkstra::Solve()
{
	int k, val, x;
	for (int i = 2; i <=nrNoduri; i++)
		drum[i] = INF;

	T.insert(make_pair(0, 1));

	while (T.size() > 0)
	{
		val = (*T.begin()).first, x = (*T.begin()).second;
		T.erase(*T.begin());
		for(int i = 0 ; i < vecini[x].size(); i++)
			if (drum[vecini[x][i]] > val + cost[x][i])
				drum[vecini[x][i]] = val + cost[x][i], T.insert(make_pair(drum[vecini[x][i]], vecini[x][i]));
	}
}

void Dijkstra::Output()
{
	ofstream OUT ("dijkstra.out");

	for (int i = 2; i <= nrNoduri; i++)
		if(drum[i] == INF)
			OUT << "0" << " ";
		else
			OUT << drum[i] << " ";
	OUT << endl;

	OUT.close();
}

int main()
{
	Dijkstra dij;
	dij.Solve();
	dij.Output();

}