#include "cyberland.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int KC = 70;

#define EL pair<__int128_t, int>
#define pb push_back

struct pq_promax {
    priority_queue<EL, vector<EL>, greater<>> add_, del_;
    // this is PQ for minimum, if you want maximum delete greater<>
    pq_promax() = default;
    void add(EL x) {
        add_.push(x);
    }
    void del(EL x) {
        del_.push(x);
    }
    EL get() {
        while (del_.size() && del_.top() == add_.top()) del_.pop(), add_.pop();
        if (add_.size()) return add_.top();
        return make_pair((__int128_t)-1, -1);
    }
};

double solve(int32_t N, int32_t M, int32_t K, int32_t H, vector<int32_t> x, vector<int32_t> y, vector<int32_t> c, vector<int32_t> arr) {
    vector<vector<int>> GR(N);
    for (int i = 0; i < M; i++) {
      GR[x[i]].pb(y[i]);
      GR[y[i]].pb(x[i]);
    }
    K = min(K, KC);
    vector<vector<pair<int, __int128_t>>> g(2 * N * (K + 1));
    auto encode = [&](int vt, int lvl) {
        return lvl * 2 * N + vt;
    };
    for (int i = 0; i < N; i++) {
        if (arr[i] == 2) {
            for (int j = 0; j < K; j++) {
                g[encode(i, j)].push_back({encode(i + N, j + 1), 0});
            }
        }
    }
    vector<__int128_t> pw2(K + 1, 1);
    for (int i = 1; i <= K; i++) pw2[i] = pw2[i - 1] * 2;
    for (int i = 0; i < M; i++) {
        for (int lvl = 0; lvl <= K; lvl++) {
            if ((x[i] == H || y[i] == H) && lvl > 0) continue;
            g[encode(x[i], lvl)].emplace_back(encode(y[i], lvl), c[i] * (__int128_t)1 * pw2[K - lvl]);
            g[encode(y[i], lvl)].emplace_back(encode(x[i], lvl), c[i] * (__int128_t)1 * pw2[K - lvl]);
            g[encode(x[i] + N, lvl)].emplace_back(encode(y[i], lvl), c[i] * (__int128_t)1 * pw2[K - lvl]);
            g[encode(y[i] + N, lvl)].emplace_back(encode(x[i], lvl), c[i] * (__int128_t)1 * pw2[K - lvl]);
        }
    }

    pq_promax pq;
    vector<__int128_t> dist(2 * N * (K + 1), -1);
    vector<int> used(2 * N * (K + 1), 0);
    dist[H] = 0;
    pq.add(make_pair((__int128_t)0, H));
    while (true) {
        auto rs = pq.get(); 
        //cout << (ll)rs.first << ' ' << rs.second << endl;
        if (rs.second == -1) break;
        pq.del(rs);
        used[rs.second] = 1;
        for (auto [v, w] : g[rs.second]) {
            if (!used[v] && (dist[v] == -1 || dist[v] > rs.first + w)) {
                if (dist[v] != -1) {
                    pq.del({dist[v], v});
                }
                dist[v] = rs.first + w;
                pq.add(make_pair(dist[v], v));
            }
        }
    }   

    vector<int> us2(N);
    us2[H] = 1;
    auto dfs = [&](int v, auto&&self) -> void {
        us2[v] = 1;
        for (int u : GR[v]) {
          if (!us2[u]) self(u, self);
        }
    };
    dfs(0, dfs);
    vector<int> edps = {0};
    for (int i = 0; i < N; i++) {
      if (us2[i] && arr[i] == 0) edps.pb(i);
    }
    __int128_t ans = (__int128_t)1000000000000000 * pw2[K];
    double dvd = pw2[K];
    for (int lvl = K; lvl >=0; lvl--) {
        for (int vt : edps) {
            if (dist[encode(vt, lvl)] != -1) {
              ans = min(ans, dist[encode(vt, lvl)]); 
            }
        }
    }
    return (ans == (__int128_t)1000000000000000 * pw2[K] ? -1 : ans / dvd);
}