#include "cyberland.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define MAXN 100005
vector<int> edge[MAXN];
vector<int> lian[MAXN];
bool ok[MAXN];
double dis[75][MAXN];
bool vis[75][MAXN];
struct kkk {
    int id;
    int ceng;
    double w;
    friend bool operator <(kkk ano1, kkk ano2) {
        if (ano1.ceng == ano2.ceng)
            return ano1.w > ano2.w;
        else
            return ano1.ceng > ano2.ceng;
    }
};
priority_queue<kkk> qq;
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) {
	K = min(K,70);
    for (int i = 0; i < N; i++)
        edge[i].clear(), lian[i].clear();

    for (int i = 0; i < N; i++)
        ok[i] = 0;

    for (int i = 0; i < M; i++) {
        edge[x[i]].push_back(y[i]);
        edge[y[i]].push_back(x[i]);
        lian[x[i]].push_back(c[i]);
        lian[y[i]].push_back(c[i]);
    }

    queue<int> q;
    q.push(0);

    while (q.size()) {
        int nowx = q.front();
        q.pop();

        if (ok[nowx])
            continue;

        ok[nowx] = 1;

        if (nowx == H)
            continue;

        for (int v : edge[nowx]) {
            q.push(v);
        }
    }

    if (!ok[H])
        return -1;

    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= N; j++)
            dis[i][j] = 1e16, vis[i][j] = 0;
    }

    while (qq.size())
        qq.pop();

    for (int i = 0; i < N; i++) {
        if (arr[i] == 0 && ok[i] == 1) {
            qq.push((kkk) {
                i, 0, 0
            });
            dis[0][i] = 0;
        }
    }

    qq.push((kkk) {
        0, 0, 0
    });
    dis[0][0] = 0;
    double ans = 1e16;
    int cengok[100];
    memset(cengok, 0, sizeof(cengok));

    while (qq.size()) {
        int nowx = qq.top().id, ceng = qq.top().ceng;
        qq.pop();

        if (cengok[ceng])
            continue;

        if (vis[ceng][nowx])
            continue;

        vis[ceng][nowx] = 1;
		if(nowx == H) continue;

        for (int vv = 0; vv < edge[nowx].size(); vv++) {
            int v = edge[nowx][vv];
			int w = lian[nowx][vv];
            if (dis[ceng][v] > dis[ceng][nowx] + w) {
                dis[ceng][v] = dis[ceng][nowx] + w;
                qq.push((kkk) {
                    v, ceng, dis[ceng][v]
                });
            }

            if (arr[v] == 2 && dis[ceng + 1][v] > (dis[ceng][nowx] + w) / 2.0 && ceng < K) {
                dis[ceng + 1][v] = (dis[ceng][nowx] + w) / 2.0;
                qq.push((kkk) {
                    v, ceng + 1, dis[ceng + 1][v]
                });
            }
        }
    }
	for(int i = 0; i <= K; i++) ans = min(ans,dis[i][H]);
    return ans;
}