#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
constexpr double inf = 1e18;
vector<vector<pair<int, double>>> g;
vector<double> get(int t, int n, int skip, vector<pair<int, int>> &p) {
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
vector<double> d(n, inf);
p[t] = {-1, 0};
d[t] = 0;
pq.push({0, t});
while (!pq.empty()) {
auto [k, u] = pq.top();
pq.pop();
if (k > d[u]) continue;
for (auto [v, w] : g[u]) {
if (v == skip) continue;
if (d[v] > k + w) {
p[v] = {u, w};
d[v] = k + w;
pq.push({d[v], v});
}
}
}
return d;
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
g.assign(n, {});
for (int i = 0; i < m; i++) {
g[x[i]].push_back({y[i], (arr[y[i]] == 2 ? (double)c[i] / 2 : c[i])});
g[y[i]].push_back({x[i], (arr[x[i]] == 2 ? (double)c[i] / 2 : c[i])});
}
vector<pair<int, int>> p(n);
vector<double> t = get(0, n, -1, p);
vector<double> s = get(0, n, h, p);
vector<double> d = get(h, n, 0, p);
if (t[h] == inf) {
return -1;
}
double ans = t[h];
int pos = 0;
for (int i = 1; i < n; i++) {
if (arr[i] == 0 && s[i] != inf) {
if (d[i] < ans) {
ans = d[i];
pos = i;
}
}
}
vector<double> w;
if (pos == 0) {
get(h, n, -1, p);
int u = pos;
while (u != h) {
if (arr[p[u].first] == 2) {
w.push_back(p[u].second);
}
u = p[u].first;
}
} else {
int u = pos;
while (u != h) {
if (arr[p[u].first] == 2) {
w.push_back(p[u].second);
}
u = p[u].first;
}
}
sort(w.begin(), w.end());
for (int i = 0; i < (int)w.size() - k; i++) {
ans += w[i];
}
return ans;
}
