Sem_2_Task_2

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

struct Edge;

const size_t INF = size_t(1e12);

namespace {
    using NumsVec = std::vector<size_t>;
    using VecNumsVec = std::vector<NumsVec>;
    using BoolVec = std::vector<bool>;
    using EdgeVec = std::vector<Edge>;
}

struct Edge {
    Edge() = default;
    Edge(std::pair<size_t, size_t> edge) : from(edge.first), to(edge.second) {};
    Edge(size_t i, size_t j, size_t w) : from(i), to(j), w(w) {};

    bool operator==(const Edge& other) const {
        return from == other.from && to == other.to;
    }

    Edge Reverse() const {
        return {to, from, w};
    }

    size_t from = 0;
    size_t to = 0;
    size_t w = 0;
};

std::istream& operator>>(std::istream& input, Edge& edge) {
    input >> edge.from >> edge.to >> edge.w;
    --edge.from;
    --edge.to;
    return input;
}

void InputEdges(std::vector<Edge>& edges) {
    for (auto& edge : edges) {
        std::cin >> edge;
    }
}

template<>
struct std::hash<Edge> {
    size_t operator()(const Edge& p) const {
        return p.from * p.to;
    }
};

std::ostream& operator<<(std::ostream& output, NumsVec& vec) {
    for (auto elem : vec) {
        std::cout << elem + 1 << " ";
    }
    return output;
}

struct Graph {
    Graph(size_t n) : size(n), neighbours(n), visited(n, false), color(n, 0),
    top_sort(n, 0), top_sort_pos(n - 1), d(n, INF) {};

    Graph(size_t n, EdgeVec& edges) : size(n), neighbours(n), visited(n, false), color(n, 0),
    top_sort(n, 0), top_sort_pos(n - 1), d(n, INF), p(n, INF) {
        for (auto edge : edges) {
            neighbours[edge.from].push_back(edge);
            neighbours[edge.to].push_back(edge.Reverse());
        }
    };
    size_t size = 0;
    bool cycle = false;

    std::vector<EdgeVec> neighbours;
    BoolVec visited;
    NumsVec color;
    NumsVec top_sort;
    NumsVec d;
    NumsVec p;
    size_t top_sort_pos = 0;
};

std::pair<size_t, size_t> Dijkstra(Graph& g, NumsVec s, NumsVec f) {
    std::set<std::pair<size_t, size_t>> vert;
    for (auto v : s) {
        g.d[v] = 0;
        vert.insert({g.d[v], v});
    }
    while (!vert.empty()) {
        size_t v = vert.begin()->second;
        vert.erase(vert.begin());
        for (auto edge : g.neighbours[v]) {
            if (g.d[edge.to] > g.d[v] + edge.w) {
                vert.erase({g.d[edge.to], edge.to});
                g.d[edge.to] = g.d[v] + edge.w;
                g.p[edge.to] = v;
                vert.insert({g.d[edge.to], edge.to});
            }
        }
    }
    size_t ans = INF;
    size_t v_ans = 0;
    for (size_t v : f) {
        if (ans > g.d[v]) {
            ans = g.d[v];
            v_ans = v;
        }
    }
    return {ans, v_ans};
}

size_t FindParent(Graph& g, size_t v) {
    while (g.p[v] != INF) {
        v = g.p[v];
    }
    return v;
}

int main() {
    size_t n;
    size_t m;
    std::cin >> n >> m;
    NumsVec cities_a;
    NumsVec cities_b;
    for (size_t v = 0; v < n; ++v) {
        size_t city;
        std::cin >> city;
        if (city == 1) {
            cities_a.push_back(v);
        } else if (city == 2) {
            cities_b.push_back(v);
        }
    }
    EdgeVec edges(m);
    InputEdges(edges);
    Graph g(n, edges);
    auto [ans, v] = Dijkstra(g, cities_a, cities_b);
    if (ans == INF) {
        std::cout << -1;
    } else {
        std::cout << FindParent(g, v) + 1 << " " << v + 1 << " " << ans;
    }
}