#include <bits/stdc++.h>
using namespace std;
using ll=long long;
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,double>>> adj(N);
for (int i=0;i<M;i++) {
adj[x[i]].pb({y[i],(double)c[i]});
adj[y[i]].pb({x[i],(double)c[i]});
}
vector<vector<double>> distance(N+1,vector<double>(K+1,(double)INF));
vector<vector<bool>> processed(N+1,vector<bool>(K+1));
priority_queue<tuple<double,int,int>> q;
distance[0][0]=0;
q.push({0.0,0,0});
while (!q.empty()) {
auto [ignore,a,k]=q.top(); q.pop();
if (processed[a][k]) continue;
processed[a][k]=true;
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]) {
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});
}
}
}
}
double ans=(double)INF;
for (int i=0;i<=K;i++) ans=min(ans,distance[H][i]);
return ans;
}
