// Disjkstra.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

//#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define INF 0x3f3f3f3f 
class Graph {
private:
	vector<vector<pair<int, int>>>adjacencyMatrix ;
	deque<int> dijkstra;
	deque<bool> discovered;
	int nVertices, nEdges;
public:
	void initAdjacencyMatrix() {
		for (int i = 0; i <= nVertices; ++i) {
			vector<pair<int, int>> vertices;
			discovered.push_back(false);
			dijkstra.push_back(INF);
			for (int j = 0; j <= nVertices; ++j)
			     vertices.push_back(make_pair(0, INF));
			adjacencyMatrix.push_back(vertices);
		}
		
	}
	void readAdjacencyMatrix(int nVertices, int nEdges) {
		int x, y, cost;
		this->nVertices = nVertices;
		this->nEdges = nEdges;
		initAdjacencyMatrix();
		for (int i = 1; i <= nEdges; ++i) {
			fin >> x >> y >> cost;
			pair<int, int> p;
			p = make_pair(1, cost);
			adjacencyMatrix[x][y] = p;
			//adjacencyMatrix[y][x] = p;
		}
	}
	void printAdjacencyMatrix() {
		for (int i = 0; i <= nVertices; ++i) {
			fout << i << endl;
			auto it = adjacencyMatrix[i].begin();
			while (it != adjacencyMatrix[i].end()) {
				fout << it->first;
				++it;
			}
			fout << endl;
		}
			
	}

	void dijkstraAlgorithm(int start) {
		dijkstra[start] = 0;
		int v = start;
		while (discovered[v] == false) {
			discovered[v] = true;
			int min = INF;
			for (int i = 1; i <= nVertices; ++i) {
				if (adjacencyMatrix[v][i].first == 1) {
					if (adjacencyMatrix[v][i].second + dijkstra[v] < dijkstra[i]) {
						dijkstra[i] = adjacencyMatrix[v][i].second + dijkstra[v];
					}
				}
			}
			int v = 1;
			for (int i = 1; i <= nVertices; ++i) {
				if(dijkstra[i] < min && discovered[i] == false && adjacencyMatrix[v][i].first == 1){
						min = dijkstra[i];
						v = i;
					}
						
			}
			
		}
		for (int i = 2; i <= nVertices; ++i)
			if (dijkstra[i] == INF)
				fout << "0 ";
			else
			fout << dijkstra[i] << " ";
	}
};
int main()
{
	int nVertices, nEdges;
	fin >> nVertices >> nEdges;
	Graph g;
	g.readAdjacencyMatrix(nVertices, nEdges);
	g.dijkstraAlgorithm(1);
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file