#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<ll, ld> pd;
typedef pair<ld, ll> pd2;
typedef pair<string, ll> psi;
typedef pair<ll, ll> pi;
typedef pair<ld, pi> pdi;
const long double INF = 1e18;
struct compare
{
bool operator() (pd2 const& a, pd2 const& b)
{
return a.f>b.f; // least element come out first
}
};
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)
{
ld ans = INF;
ll n = N;
vector<pd> adj[100005];
for (ll i=0; i<M; ++i)
{
adj[x[i]].pb(mp(y[i], (ld) c[i]));
adj[y[i]].pb(mp(x[i], (ld) c[i]));
}
vector<ld> dist(n+5, INF);
priority_queue<pd2, vector<pd2>, compare> pq;
dist[0] = 0.0;
pq.push(mp(0, 0));
for (ll i=min(70, K); i>=0; --i)
{
priority_queue<pd2, vector<pd2>, compare> newpq;
vector<ld> newdist(n+5, INF);
while (pq.size())
{
ll city = pq.top().s;
ld cost = pq.top().f;
pq.pop();
if (cost>dist[city] || city==H) continue;
for (pd u: adj[city])
{
if (arr[u.f]==0 && dist[u.f]>0.0)
{
dist[u.f] = 0.0;
pq.push(mp(0.0, u.f));
}
ld newcost = cost + (ld) u.s;
if (newcost<dist[u.f])
{
dist[u.f] = newcost;
pq.push(mp(dist[u.f], u.f));
}
if (arr[u.f]==2 && i>0 && (newcost)/ (ld) 2.0 < newdist[u.f])
{
newdist[u.f] = newcost/(ld) 2.0;
newpq.push(mp(newdist[u.f], u.f));
}
}
}
ans = min(ans, dist[H]);
dist = newdist;
pq = newpq;
}
return (ans==INF)?-1: ans;
}
