#include "bits/stdc++.h"
#include "cyberland.h"
#include "stub.cpp"
using namespace std;
#define ff first
#define ss second
const long long INF = 1e16 + 6;
vector <vector <pair <int, int>>> v;
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> a) {
double ans = INF;
v.clear();
v.resize(n+1);
for(int i = 0; i < m; i++) {
v[x[i]].push_back({y[i], c[i]});
v[y[i]].push_back({x[i], c[i]});
}
vector <vector <double>> dis(n+1, vector <double> (k+1, INF));
priority_queue <pair <double, pair <int, int>>> q;
dis[0][0] = 0;
q.push({0, {0, 0}});
while(!q.empty()) {
double ds = -q.top().ff;
int i = q.top().ss.ff, cn = q.top().ss.ss;
q.pop();
if(i == h or dis[i][cn] != ds) continue;
for(auto [j, w] : v[i]) {
double dss = ds + w;
if(dis[j][cn] > dss) {
dis[j][cn] = dss;
q.push({-dss, {j, cn}});
}
if(a[j] == 0 and dis[j][cn] != 0) {
dis[j][cn] = 0;
q.push({0, {j, cn}});
}
if(a[j] == 2 and cn < k) {
dss /= 2;
if(dis[j][cn+1] > dss) {
dis[j][cn+1] = dss;
q.push({-dss, {j, cn+1}});
}
}
}
}
for(int i = 0; i <= k; i++) {
ans = min(ans, dis[h][i]);
}
return (ans == INF ? -1 : ans);
}
