#include "pch.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>

constexpr auto INF = 0x3f3f3f3f;

using namespace std;

class graph {
	int nodes, edges;
	vector<vector<pair<int, int>>> list;

public:
	graph(int);
	graph(string);

	void addEdgeO(int, int, int);
	void dijkstra(int);
};

graph::graph(int v) {
	this->nodes = v;
	list.resize(v + 1);
}

graph::graph(string file) {
	ifstream f(file);

	f >> nodes >> edges;
	list.resize(nodes + 1);
	for (int i = 0; i < edges; i++) {
		int x, y, c;
		f >> x >> y >> c;
		addEdgeO(x, y, c);
	}

	f.close();
}

void graph::addEdgeO(int x, int y, int c = 0) {
	list[x].push_back(make_pair(y, c));
}
void graph::dijkstra(int src) {
	vector<int> dist(nodes + 1, INF);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	pq.push(make_pair(0, src));
	dist[src] = 0;

	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();

		for (auto it : list[u]) {
			int w = it.second;
			int v = it.first;

			if (dist[v] > dist[u] + w)
			{
				dist[v] = dist[u] + w;
				pq.push(make_pair(dist[v], v));
			}
		}
	}

	ofstream g("dijkstra.out");
	for (int i = 2; i <= nodes; i++) {
		g << ((dist[i] != INF) ? dist[i] : 0) << " ";
	}
	g.close();
}

int main()
{
	graph g("dijkstra.in");
	g.dijkstra(1);
}