#include<iostream>
#include<list>
#include<functional>
#include<vector>
#include<unordered_set>
#include<climits>
#include<fstream>
using namespace std;

int getUnvisitedVertexWithMinDist(long dist[], int size, unordered_set<int> &unvisitedVertices) {
	unordered_set<int>::iterator it = unvisitedVertices.begin();
	int minVertex = *it;
	long minDist = dist[minVertex];
	for (;it != unvisitedVertices.end(); it++) {
		long distance = dist[*it];
		if (distance < minDist) {
			minDist = distance;
			minVertex = *it;
		}
	}
	return minVertex;
}

void dijkstra(vector<vector<pair<int,int>>> &adjList, int numNodes, int source) {
	unordered_set<int> unvisitedVertices;
	long *dist = new long[numNodes + 1];
	for (int i = 1; i <= numNodes; i++) {
		dist[i] = LONG_MAX;
		unvisitedVertices.insert(i);
	}
	dist[source] = 0;
	while (!unvisitedVertices.empty()) {
		int minVertex = getUnvisitedVertexWithMinDist(dist, numNodes+1, unvisitedVertices);
		unvisitedVertices.erase(minVertex);
		vector<pair<int, int>> neighbors = adjList[minVertex];
		for (int i = 0; i < neighbors.size(); i++) {
			pair<int,int> n = neighbors[i];
			long altDist = dist[minVertex] + n.second;
			if (altDist < dist[n.first]) {
				dist[n.first] = altDist;
			}
		}
	}

	ofstream out("dijkstra.out");

	for (int i = 2; i <= numNodes; i++) {
		out << dist[i] << " ";
	}
	out << endl;
}

int main() {
	ifstream in("dijkstra.in");
	int numNodes, numEdges;
	in >> numNodes >> numEdges;
	vector<vector<pair<int, int>>> adjList(numNodes + 1);
	for (int i = 1; i <= numEdges; i++) {
		int source, dest, weight;
		in >> source >> dest >> weight;
		adjList[source].push_back(make_pair(dest, weight));
	}
	dijkstra(adjList, numNodes, 1);
	
}