#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const double inf = 2e14;
const int maxn=1e5+5;
int h;
vector<pair<int,double>>E[maxn];
vector<double>Dijkstra(int n,vector<int>s, vector<double>ds){
priority_queue<pair<double,int>>p;
vector<bool>vis(n,0);
for(auto i : s){
p.push({-ds[i], i});
}
while(!p.empty()){
int x = p.top().second;
p.pop();
if(vis[x]) continue;
vis[x] = 1;
if(x == h) continue;
for(auto i : E[x]){
int to = i.first;
double w = i.second;
if(ds[to] > ds[x] + w){
ds[to] = ds[x] + w;
p.push({-ds[to], to});
}
}
}
return ds;
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
h = H;
vector<int>twos;
for(int i = 0;i < N;i++){
E[i].clear();
if(arr[i] == 2) twos.push_back(i);
}
for(int i = 0;i < M;i++){
E[x[i]].push_back({y[i],c[i]});
E[y[i]].push_back({x[i],c[i]});
}
vector<int>now;
now.push_back(0);
vector<double>dis(N,inf);
dis[0] = 0;
dis = Dijkstra(N, now, dis);
dis[0] = 0;
for(int i = 1;i < N;i++){
if(arr[i] == 0 and dis[i] < inf-2){
now.push_back(i);
dis[i] = 0;
}
else dis[i] = inf;
}
double ans = inf;
for(int i = 1;i <= K;i++){
dis = Dijkstra(N, now, dis);
ans = min(ans, dis[H]);
if(arr[H] == 2) ans = min(ans, dis[H] / 2);
vector<double>ndis(N,inf);
for(auto t : twos){
if(t == H) continue;
double nw = dis[t] / 2;
for(auto j : E[t]){
int to = j.first;
double w = j.second;
ndis[to] = min(ndis[to],nw + w);
}
}
vector<int>ns;
for(int j = 0;j < N;j++){
if(ndis[j] < inf-2){
ns.push_back(j);
}
}
now = ns;
dis = ndis;
}
dis = Dijkstra(N, now, dis);
ans = min(ans, dis[H]);
if(ans >= inf-2) ans = -1;
return ans;
}
