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

//#include "pch.h"
#include <iostream>
#include <fstream>
#include <math.h>
#include <queue>
#include <deque>
# define INF 0x3f3f3f3f 
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct vertex {
	int value;
	int weight;
	vertex * next;
};
class Graph {
private:
	deque<vertex *> adjacencyList;
	deque<int>degree;
	deque<bool>processed;
	deque<bool>discovered;
	int nVertices, nEdges;

	bool directed;
public:
	void initialiseGraph() {
		for (int i = 1; i <= nVertices + 1; ++i) {
			adjacencyList.push_back(nullptr);
			degree.push_back(0); 
			processed.push_back(false);
			discovered.push_back(false);
		}
	}
	void readGraph(int nVertices, int nEdges, bool directed) {
		int x, y, weight;
		this->nVertices = nVertices;
		this->nEdges = nEdges;
		this->directed = directed;
		initialiseGraph();
		for (int i = 1; i <= nEdges; ++i) {
			fin >> x >> y >> weight;
			insertVertex(y, x, weight, directed);
		}
	}
	void insertVertex(int x, int y, int weight, bool directed) {
		if (x == y)
			return;
		vertex * newVertex = new vertex;
		newVertex->value = x;
		newVertex->weight = weight;
		newVertex->next = adjacencyList[y];
		adjacencyList[y] = newVertex;
		degree[x]++;
		if (directed == false) {
			insertVertex(y, x, weight, !directed);
		}
	}
	void printGraph() {
		vertex* edgeNode;
		for (int i = 0; i <= nVertices; ++i) {
			if (adjacencyList.at(i) != nullptr) {
				fout << "\n Adjacency list of vertex " << i << "\n head ";
				edgeNode = adjacencyList.at(i);
				while (edgeNode != nullptr) {
					fout << edgeNode->value << " ";
					edgeNode = edgeNode->next;
				}
				fout << endl;
			}
		}
	}
	void dijkstra() {
		struct compare {
		public:
			bool operator()(const pair<int, int> a, const pair<int, int> b) {
				return a.second < b.second;
			}
		};
		vector<int> dij(nVertices + 1, INF);
		priority_queue < pair<int,int>, vector<pair<int, int>>, compare > vertices;
		vertices.push(make_pair(1, 0));
		dij[1] = 0;
		while (!vertices.empty()) {
			int x = vertices.top().first;
			vertices.pop();
			
			vertex * v = adjacencyList[x];
			while (v != nullptr) {
				
				if (discovered[v->value] == false) {
					dij[v->value] = min(dij[x] + v->weight, dij[v->value]);
					discovered[v->value] = true;
					vertices.push(make_pair(v->value, dij[v->value]));
				}
				if (processed[v->value] == false || directed == true) {
					dij[v->value] = min(dij[x] + v->weight, dij[v->value]);
				}
				v = v->next;
			}
         processed[x] = true;
		}
		for (int i = 2; i <= nVertices; i++)
			if (dij[i] == INF)
				fout << "0 ";
			else
			fout << dij[i] << " ";
	}
};
int main()
{
	int nVertices, nEdges;
	fin >> nVertices >> nEdges;
	Graph g;
	g.readGraph(nVertices, nEdges, true);
	//g.printGraph();
	g.dijkstra();

	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