#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll INF=1e18;
#define pb push_back
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
vector<vector<pair<int,ld>>> adj(N);
for (int i=0;i<M;i++) {
adj[x[i]].pb({y[i],(ld)c[i]});
adj[y[i]].pb({x[i],(ld)c[i]});
}
vector<vector<ld>> distance(N+1,vector<ld>(K+1,(ld)INF));
vector<vector<bool>> processed(N+1,vector<bool>(K+1));
priority_queue<tuple<ld,int,int>,vector<tuple<ld,int,int>>,greater<tuple<ld,int,int>>> q;
for (int i=0;i<=K;i++) distance[0][i]=0;
q.push({0.0,0,0});
while (!q.empty()) {
auto [ignore,a,k]=q.top(); q.pop();
if (a==H) continue;
if (processed[a][k]) continue;
processed[a][k]=true;
K=min(K,30);
for (auto u : adj[a]) {
auto [b,w]=u;
if (arr[b]==0) {
if (distance[b][k]!=0) {
distance[b][k]=0;
q.push({distance[b][k],b,k});
}
} else if (arr[b]==2) {
if (k+1<=K) {
if ((distance[a][k]+w)/2<distance[b][k+1]) {
distance[b][k+1]=(distance[a][k]+w)/2;
q.push({distance[b][k+1],b,k+1});
}
}
if (distance[a][k]+w<distance[b][k]) {
distance[b][k]=distance[a][k]+w;
q.push({distance[b][k],b,k});
}
} else {
if (distance[a][k]+w<distance[b][k]) {
distance[b][k]=distance[a][k]+w;
q.push({distance[b][k],b,k});
}
}
}
}
ld ans=(ld)INF;
for (int i=0;i<=K;i++) ans=min(ans,distance[H][i]);
ans=(ans==(ld)INF) ? -1 : ans;
return ans;
}
