#include "cyberland.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//ꜰᴏʀ ɪɴᴅᴇᴇᴅ, ᴡɪᴛʜ ʜᴀʀᴅꜱʜɪᴘ ᴄᴏᴍᴇꜱ ᴇᴀꜱᴇ. ɪɴᴅᴇᴇᴅ, ᴡɪᴛʜ ʜᴀʀᴅꜱʜɪᴘ ᴄᴏᴍᴇꜱ ᴇᴀꜱᴇ. [94:5–6]
//Author: Sazid Hasan (@iamsazidh)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
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) {
K = min(100, K);
vector<vector<pair<int, int>>> adj(N);
for(int i = 0; i < M; i++){
// if(x[i]==H || y[i]==H) continue;
adj[x[i]].push_back({y[i], c[i]});
adj[y[i]].push_back({x[i], c[i]});
}
vector<vector<vector<dl>>> dp(2, vector<vector<dl>>(K+4, vector<dl>(N, DBL_MAX))); // dp[power1][power2count][node]
priority_queue<
pair<pair<pair<int, int>, double>, int>,
vector<pair<pair<pair<int, int>, double>, int>>,
greater<pair<pair<pair<int, int>, double>, int>>
> pq; // power1, power2, cost, node
pq.push({{{0, 0}, 0}, 0});
while(!pq.empty()){
int p1 = pq.top().ff.ff.ff, p2 = pq.top().ff.ff.ss, node = pq.top().ss;
dl cost = pq.top().ff.ss;
pq.pop();
// if(dp[p1][p2][node]-cost < 1e-6) continue; // handle precision if error occcurs in random testtcase
for(auto x: adj[node]){
if(cost + x.ss < dp[p1][p2][x.ff]){
dp[p1][p2][x.ff] = cost + x.ss;
if(x.ff!=H) pq.push({{{p1, p2}, dp[p1][p2][x.ff]}, x.ff});
}
}
if(arr[node]==0 && dp[1][0][node]!=0){
dp[1][0][node] = 0;
pq.push({{{1, 0}, 0}, node});
}
if(arr[node]==2 && p2<K){
for(auto x: adj[node]){
if(cost/2 + x.ss < dp[p1][p2+1][x.ff]){
dp[p1][p2+1][x.ff] = cost/2 + x.ss;
if(x.ff!=H) pq.push({{{p1, p2+1}, dp[p1][p2+1][x.ff]}, x.ff});
}
}
}
}
dl ans = DBL_MAX;
for(int i = 0; i < 2; i++){
for(int j = 0; j <= K; j++) ans = min(ans, dp[i][j][H]);
}
if(ans==DBL_MAX) return -1;
return ans;
}
