// http://infoarena.ro/problema/dijkstra
#include <fstream>
#include <vector>
#include <list>
using namespace std;

#define INFINITY 0x3f3f3f3f
int nodes,edges,visited;

vector< list< pair<int,int> > > graph;
vector<int> dist;
//vector<int> father;
vector<bool> visit;

void read();
void dijkstra(int startNode);
	int findNextNode(int toAvoid);
void write();

int main() {
	read();
	dijkstra(1);
	write();

	return (0);
}

void read() {
	ifstream in("dijkstra.in");
	int from,to,lenght;
	
	in >> nodes >> edges;
	graph.resize(nodes+1);
	dist.resize(nodes+1);
	//father.resize(nodes+1);
	visit.resize(nodes+1);

	for(int i=1;i<=edges;i++) {
		in >> from >> to >> lenght;

		graph.at(from).push_back(make_pair(to,lenght));
	}

	in.close();
}

void dijkstra(int startNode) {
	dist.assign(nodes+1,INFINITY);
	dist.at(startNode) = 0;

	int toVisit = startNode;
	list< pair<int,int> >::iterator it;

	for(;;) {
		if(dist.at(toVisit) == INFINITY)
			break;

		for(it=graph.at(toVisit).begin();it!=graph.at(toVisit).end();it++)
			if(!visit.at(it->first))
				if(dist.at(toVisit) + it->second < dist.at(it->first)) {
					dist.at(it->first) = dist.at(toVisit) + it->second;
					//father.at(it->first) = toVisit;
				}

		visit.at(toVisit) = true;
		visited++;

		if(visited == nodes)
			break;

		toVisit = findNextNode(startNode);
	}
}

int findNextNode(int toAvoid) {
	pair<int,int> toVisitNext;
	toVisitNext.second = INFINITY + 1;

	for(int i=1;i<toAvoid;i++)
		if(!visit.at(i) && (dist.at(i) < toVisitNext.second))
			toVisitNext = make_pair(i,dist.at(i));

	for(int i=toAvoid+1;i<=nodes;i++)
		if(!visit.at(i) && (dist.at(i) < toVisitNext.second))
			toVisitNext = make_pair(i,dist.at(i));

	return toVisitNext.first;
}

void write() {
	ofstream out("dijkstra.out");

	for(int i=2;i<=nodes;i++)
		if(dist.at(i) == INFINITY)
			out << "0 ";
		else
			out << dist.at(i) << " ";

	out.close();
}