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

const int INFINITY = 1001;
int nodes,edges;
int visited;
int tentativeDistance;
pair<int,int> toVisitNext;
vector< list< pair<int,int> > > graph;
vector<int> dist;
vector<bool> visit;

void read();
void dijkstra(int startNode);
	void relaxEdges(int node);
	int findNextNode();
void write();

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

	return (0);
}

void read() {
	ifstream in("dijkstra.in");
	int from,to,cost;

	in >> nodes >> edges;
	graph.resize(nodes+1);
	dist.resize(nodes+1);
	visit.resize(nodes+1);

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

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

	in.close();
}

void dijkstra(int startNode) {
	dist.assign(dist.size(),INFINITY);
	dist.at(startNode) = NULL;

	relaxEdges(startNode);

	while(visited != nodes)
		relaxEdges(findNextNode());
}

void relaxEdges(int node) {
	for(;;) {
		toVisitNext = make_pair(NULL,INFINITY);

		for(list< pair<int,int> >::iterator it=graph.at(node).begin();it!=graph.at(node).end();it++) {
			tentativeDistance = dist.at(node) + it->second;

			if(tentativeDistance < dist.at(it->first))
				dist.at(it->first) = tentativeDistance;

			if(it->second < toVisitNext.second)
				toVisitNext = make_pair(it->first,it->second);
		}

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

		if(!toVisitNext.first)
			break;
		else
			if(visit.at(toVisitNext.first))
				break;
			else
				node = toVisitNext.first;
	}
}

int findNextNode() {
	toVisitNext = make_pair(NULL,INFINITY);

	for(int i=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) << " ";
}