#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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)
{
vector < vector < pair < int, int > > > adj (n);
for (int i = 0; i < m; ++i)
{
adj[x[i]].push_back ({ c[i], y[i] });
adj[y[i]].push_back ({ c[i], x[i] });
}
if (n <= 3)
{
vector < double > da (n, -1);
auto dfs = [&] (auto self, int v, int p, double d) -> void
{
if (arr[v] == 0) d = 0;
if (arr[v] == 2) d /= 2;
if (da[v] < 0 || da[v] > d) da[v] = d;
if (v == h) return;
for (auto &x : adj[v])
if (x.second != p)
self (self, x.second, v, d + x.first);
};
dfs (dfs, 0, -1, 0);
return da[h];
}
priority_queue < pair < ll, int > > q;
q.push ({ 0ll, 0 });
vector < ll > sda (n, -1);
while (q.size ())
{
auto x = q.top ();
q.pop ();
if (sda[x.second] != -1) continue;
sda[x.second] = -x.first;
if (x.second == h) continue;
for (auto &y : adj[x.second])
q.push ({ x.first - y.first, y.second });
}
if (sda[h] == -1) return -1;
set < int > rz;
rz.insert (0);
for (int i = 0; i < n; ++i)
if (arr[i] == 0 && sda[i] > 0)
rz.insert (i);
set < int > rd;
for (int i = 0; i < n; ++i)
if (arr[i] == 2 && sda[i] > 0)
rd.insert (i);
vector < ll > eda (n, -1);
q.push ({ 0ll, h });
while (q.size ())
{
auto x = q.top ();
q.pop ();
if (eda[x.second] != -1) continue;
eda[x.second] = -x.first;
for (auto &y : adj[x.second])
q.push ({ x.first - y.first, y.second });
}
double ans = 1e18;
for (auto &x : rz) ans = min (ans, (double) eda[x]);
// vector < ll > dda (n, -1);
// vector < ll > bfd (n, (ll) 1e18);
// priority_queue < pair < ll, pair < int, int > > > pq;
// for (auto &x : rd) pq.insert ({ 0ll, make_pair (x, x) });
// while (pq.size ())
// {
// auto x = q.top ();
// q.pop ();
// if (x.second.first == h) continue;
// if (dda[x.second.first] == -1 || dda[x.second.first] == -x.first)
// bfd[x.second.second] = min (bfd[x.second.second], -x.first);
// if (dda[x.second.first] != -1) continue;
// dda[x.second.first] = -x.first;
// for (auto &y : adj[x.second.first])
// q.push ({ x.first - y.first, make_pair (y.second, x.second.first) });
// }
// for (auto &x : rd)
// {
// bfd[x]
// }
return ans;
}
