#include "cyberland.h"
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <bitset>
#include <cassert>
#define ll long long
#define fr first
#define sc second
#define pb push_back
using namespace std;
const int N = 100005;
const ll oo = 1000000000000000, MOD = 1000000007;
vector<pair<int, int>> g[N];
double dist[N][67];
double solve(int n, int m, int k, int h, std::vector<int> vec1, std::vector<int> vec2, std::vector<int> vec3, std::vector<int> a) {
k = min(k, 65);
for (int i = 0; i < n; ++i) {
g[i].clear();
}
for (int i = 0; i < m; ++i) {
g[vec1[i]].pb({ vec2[i],vec3[i] });
g[vec2[i]].pb({ vec1[i],vec3[i] });
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
dist[i][j] = oo;
}
}
dist[0][0] = 0;
priority_queue<pair<double, pair<int, int>>> st;
st.push({ -dist[0][0],{0,0} });
while (st.empty() != 1) {
pair<double, pair<int, int>> p = st.top();
st.pop();
int k1 = p.sc.fr;
int u = p.sc.sc;
double val = -p.fr;
if (dist[u][k1] != val || u == h) {
continue;
}
double val2 = val / (2.0);
for (pair<int, int> num : g[u]) {
int h = num.fr;
int w = num.sc;
if (k1 < k) {
if (a[u] == 0) {
if (dist[h][0] > w) {
dist[h][0] = w;
st.push({ -dist[h][0],{0,h} });
}
}
else {
if (a[u] == 2) {
if (dist[h][k1 + 1] > val2 + w) {
dist[h][k1 + 1] = val2 + w;
st.push({ -dist[h][k1 + 1],{k1 + 1,h} });
}
if (dist[h][k1] > val + w) {
dist[h][k1] = val + w;
st.push({ -dist[h][k1],{k1,h} });
}
}
else {
if (dist[h][k1] > val + w) {
dist[h][k1] = val + w;
st.push({ -dist[h][k1],{k1,h} });
}
}
}
}
else {
if (a[u] == 0) {
if (dist[h][0] > w) {
dist[h][0] = w;
st.push({ -dist[h][0],{0,h} });
}
}
else {
if (a[u] == 2) {
if (dist[h][k1] > val + w) {
dist[h][k1] = val + w;
st.push({ -dist[h][k1],{k1,h} });
}
}
else {
if (dist[h][k1] > val + w) {
dist[h][k1] = val + w;
st.push({ -dist[h][k1],{k1,h} });
}
}
}
}
}
}
double mn = oo;
for (int i = 0; i <= k; ++i) {
mn = min(mn, dist[h][i]);
}
if (mn == oo) {
return -1;
}
return mn;
}
