#include "cyberland.h"

#include <vector>
#include <set>
#include <iostream>
#include <functional>

using namespace std;

const long double INF = 1e18;

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
    int comp[N], cur = 0;
    bool used[N];
    for(int i = 0; i < N; i++) used[i] = false;
    vector<pair<int, int >> g[N];
    for(int i = 0; i < M; i++){
        g[x[i]].emplace_back(y[i], c[i]);
        g[y[i]].emplace_back(x[i], c[i]);
    }
    function<void(int, bool)> dfs = [&](int v, bool F){
        comp[v] = cur;
        used[v] = true;
        for(auto [u, w] : g[v]){
            if(!used[u]){
                if(!F || (F && u != H))
                    dfs(u, F);
            }
        }
    };
    for(int i = 0; i < N; i++){
        if(!used[i]){
            dfs(i, false);
            cur++;
        }
    }
    if(comp[0] != comp[H]) return -1;
    for(int i = 0; i < N; i++) used[i] = false;
    cur = 0;
    for(int i = 0; i < N; i++){
        if(!used[i] && i != H){
            dfs(i, true);
            cur++;
        }
    }
    long double dist[N][K + 1];
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= K; j++){
            dist[i][j] = INF;
        }
    }
    set<pair<long double, pair<int, int>>> st;
    for(int i = 0; i < N; i++){
        if(comp[i] == comp[0] && arr[i] == 0){
            dist[i][0] = 0;
            st.insert({0, {i, 0}});
        }
    }
    dist[0][0] = 0;
    st.insert({0, {0, 0}});
    while(!st.empty()){
        auto p = *st.rbegin();
        st.erase(p);
        int v = p.second.first, k = p.second.second;
        for(auto [u, w] : g[v]){
            if(u == H) continue;
            if(dist[u][k] > dist[v][k] + w){
                st.erase({dist[u][k], {u, k}});
                dist[u][k] = dist[v][k] + w;
                st.insert({dist[u][k], {u, k}});
            }
            if(arr[u] == 2 && k + 1 <= K && dist[u][k + 1] > (dist[v][k] + w) / 2){
                st.erase({dist[u][k + 1], {u, k + 1}});
                dist[u][k + 1] = (dist[v][k] + w) / 2;
                st.insert({dist[u][k + 1], {u, k + 1}});
            }
        }
    }
    long double res = INF;
    for(auto [u, w] : g[H]){
        long double ans = INF;
        for(int j = 0; j <= K; j++) ans = min(ans, dist[u][j]);
        res = min(res, ans + w);
    }
    return res;
}