#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "cyberland.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef double ll;
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i, x, y) for(int i=x; i<y; i++)
#define FORNEG(i, x, y) for(int i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mp make_pair
#define fir first
#define sec second
vector<pair<long long,ll>> edges[100001];
ll dists[100001][71];
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
FOR(i,0,N+1) FOR(j,0,71) dists[i][j] = 1000000000000000;
FOR(i,0,N+1) edges[i].clear();
FOR(i,0,M){
edges[x[i]].push_back(mp(y[i], c[i]));
edges[y[i]].push_back(mp(x[i], c[i]));
}
priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> p;
FOR(i,0,N){
if (i==0){
dists[i][0] = 0;
p.push({0, (ll) i, 0});
}
}
while (p.size()){
ll dist = p.top()[0];
long long node = (long long) p.top()[1];
long long times = (long long) p.top()[2];
p.pop();
if (node==H) continue;
if (dists[node][times] < dist) continue;
for (auto&i : edges[node]){
if (arr[i.fir]==0){
if (dists[i.fir][times] > 0){
dists[i.fir][times] = 0;
p.push({dists[i.fir][times],(ll) i.fir, (ll) times});
}
continue;
}
if (dists[i.fir][times] > dists[node][times] + i.sec){
dists[i.fir][times] = dists[node][times] + i.sec;
p.push({dists[i.fir][times],(ll) i.fir, (ll) times});
}
if (arr[i.fir] == 2){
if (times == K || times == 70) continue;
ll newdist = (dists[node][times] + i.sec)/2;
if (dists[i.fir][times+1] > newdist){
dists[i.fir][times+1] = newdist;
p.push({dists[i.fir][times+1],(ll) i.fir, (ll) times+1});
}
}
}
}
ll ans = 1000000000000000;
FOR(i,0,min(K+1, 70)){
ans = min(ans, dists[H][i]);
}
if (ans==1000000000000000) return -1;
return ans;
}
