#include <iostream>
#include <vector>
#include <queue>


std::vector<std::vector<int>> graph_to_edges(int n, std::vector<std::vector<int>> graph) {
    std::vector<std::vector<int>> edges(n);

    for (auto i: graph) {
        int u = i[0] - 1;
        int v = i[1] - 1;

        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    return edges;
}


std::vector<std::vector<std::pair<int, int>>> weights_graph_to_edges(int n, std::vector<std::vector<int>> graph) {
    std::vector<std::vector<std::pair<int, int>>> edges(n);

    for (auto i: graph) {
        int u = i[0] - 1;
        int v = i[1] - 1;
        int c = i[2];

        edges[u].emplace_back(v, c);
        edges[v].emplace_back(u, c);
    }

    return edges;
}


std::vector<int> dfs(int n, std::vector<std::vector<int>> graph, int start_vertex) {
    std::vector<int> result(n, -1);
    std::vector<std::vector<int>> edges(graph_to_edges(n, graph));

    start_vertex -= 1;

    std::vector<int> order;
    result[start_vertex] = 0;

    dfs_inner(&order, &result, start_vertex, edges);

    return result;
}


void dfs_inner(std::vector<int>* order, std::vector<int>* result, int vertex, const std::vector<std::vector<int>>& edges) {
    order->push_back(vertex);

    for (auto next_vertex: edges[vertex]) {
        if ((*result)[next_vertex] == -1) {
            (*result)[next_vertex] = order->size();
            dfs_inner(order, result, next_vertex, edges);
        }
    }
}


std::vector<int> bfs(int n, std::vector<std::vector<int>> graph, int start_vertex) {
    std::vector<int> result(n, -1);
    std::vector<std::vector<int>> edges(graph_to_edges(n, graph));

    std::queue<int> vertexes_to_visit;
    start_vertex -= 1;
    vertexes_to_visit.push(start_vertex);
    result[start_vertex] = 0;

    while (!vertexes_to_visit.empty()) {
        int current_vertex = vertexes_to_visit.front();

        for (auto next_vertex: edges[current_vertex]) {
            if (result[next_vertex] != -1) {
                continue;
            }
            vertexes_to_visit.push(next_vertex);
            result[next_vertex] = result[current_vertex] + 1;
        }
    }

    return result;
}
const int INF = 1000000000;

std::vector<int> dijkstra(int n, std::vector<std::vector<int>> graph, int start_vertex) {
    std::vector<int> result(n, -1);
    std::vector<std::vector<std::pair<int, int>>> edges(weights_graph_to_edges(n, graph));

	std::vector<int> result(n, INF);
	result[start_vertex] = 0;
	std::vector<char> u (n);
	for (int i = 0; i < n; ++i) {
		int v = -1;
		for (int j = 0; j < n; ++j)
			if (!u[j] && (v == -1 || result[j] < result[v]))
				v = j;
		if (result[v] == INF)
			break;
		u[v] = true;

		for (size_t j = 0; j < edges[v].size(); ++j) {
			int to = edges[v][j].first, len = edges[v][j].second;
			if (result[v] + len < result[to]) {
				result[to] = result[v] + len;
			}
		}
	}

    return result;
}


int main() {
    std::vector<std::vector<int>> a{{1,2}, {2,3}, {3,4}};

}