Dijkstra

#include <utility>
#include <cstdio>
#include <vector>
#include <set>

using std :: make_pair;
using std :: vector;
using std :: pair;
using std :: set;

set< pair<int, int> > s;
vector< pair<int, int> > g[5005];
int n, m, a[5005], d[5005], p[5005], as, ae, mi = 2e9;

int main () {
        scanf ("%d%d", &n, &m);

        for (int i = 1; i <= n; i++) {
                scanf ("%d", &a[i]);
                if (a[i] == 1) {
                        s.insert (make_pair (0, i));
                        p[i] = i;
                } else {
                        d[i] = (int) 2e9;
                }
        }

        for (int i = 1; i <= m; i++) {
                int x, y, cost;
                scanf ("%d%d%d", &x, &y, &cost);
                g[x].push_back (make_pair (y, cost));
                g[y].push_back (make_pair (x, cost));
        }

        while (!s.empty ()) {
                int v = s.begin () -> second;
                s.erase (s.begin ());
                for (auto i : g[v]) {
                        int to = i.first;
                        int cost = i.second;
                        if (d[to] > d[v] + cost) {
                                if (s.count (make_pair (d[to], to))) {
                                        s.erase (make_pair (d[to], to));
                                }
                                d[to] = d[v] + cost;
                                p[to] = p[v];
                                s.insert (make_pair (d[to], to));
                        }
                }
        }

        for (int i = 1; i <= n; i++) {
                if (a[i] == 2 && mi > d[i]) {
                        as = p[i];
                        ae = i;
                        mi = d[i];
                }
        }

        if (mi == (int) 2e9) {
                puts ("-1");
        } else {
                printf ("%d %d %d\n", as, ae, mi);
        }

        return 0;
}