#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define fr first
#define er erase
#define in insert
#define sc second
#define ll long long
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define len(x) (ll) x.size()
#define all(x) x.begin(),x.end()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll maxn = 1e5 + 5;
ll n, m, k = 0;
// A suali
// #include "split.h"
// mt19937 rng(clock());
// vll g[maxn];
// pair<vll, vll>f(ll a, ll b){
// if(a > b) swap(a, b);
// // 7 balliq subtask : cycle (AC)
// // 11 balliq subtask : a = 1 (AC)
// // 22 balliq subtask : tree (AC)
// }
// vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
// n = _n;
// for(ll i = 0; i < n; i ++) g[i].clear();
// for(ll i = 0; i < len(p); i ++){
// g[p[i]].pb(q[i]), g[q[i]].pb(p[i]);
// }
// vector<int>cv(n);
// if(_a <= _c and _b <= _c){
// auto [ax, bx] = f(_a, _b);
// if(_a > _b) swap(ax, bx);
// if(len(ax) != _a) return cv;
// cv.assign(n, 3);
// for(auto i : ax) cv[i] = 1;
// for(auto i : bx) cv[i] = 2;
// }
// else if(_a <= _b and _c <= _b){
// auto [ax, cx] = f(_a, _c);
// if(_a > _c) swap(ax, cx);
// if(len(ax) != _a) return cv;
// cv.assign(n, 2);
// for(auto i : ax) cv[i] = 1;
// for(auto i : cx) cv[i] = 3;
// }
// else{
// auto [bx, cx] = f(_b, _c);
// if(_b > _c) swap(bx, cx);
// if(len(bx) != _b) return cv;
// cv.assign(n, 1);
// for(auto i : bx) cv[i] = 2;
// for(auto i : cx) cv[i] = 3;
// }
// return cv;
// }
// B suali
// Skipledim helelik
// C suali
// Observation: k = min(k, 30) olmagi besdi cunki ondan boyuk olanda menasi olmur(x <= 2^30)
vector<pair<ll, double>>g[maxn];
ll en, a[maxn];
double dis[maxn][35];
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){
n = N, m = M, k = K, en = H;
k = min(k, 30ll); // Observation 1 (line 74)
for(ll i = 0; i < n; i ++){
a[i] = arr[i];
}
for(ll i = 0; i < n; i ++){
for(ll j = 0; j <= k; j ++){
dis[i][j] = 1e15;
}
g[i].clear();
}
for(ll i = 0; i < m; i ++){
g[x[i]].pb({y[i], c[i]});
g[y[i]].pb({x[i], c[i]});
}
#define stu tuple<double, ll, ll>
priority_queue<stu, vector<stu>, greater<stu>>q;
dis[0][0] = 0;
q.push({0, 0, 0});
while(!q.empty()){
auto [tmpp, say, u] = q.top();
q.pop();
if(tmpp > dis[u][say] or u == en) continue;
for(auto [v, w] : g[u]){
if(a[u] == 0){
if(dis[v][0] > w){
dis[v][0] = w;
q.push({dis[v][0], 0, v});
}
}
else{
if(dis[v][say] > dis[u][say] + w){
dis[v][say] = dis[u][say] + w;
q.push({dis[v][say], say, v});
}
}
if(a[u] == 2 and say < k and dis[v][say + 1] > dis[u][say] / 2 + w){
dis[v][say + 1] = dis[u][say] / 2 + w;
q.push({dis[v][say + 1], say + 1, v});
}
}
}
double cv = 1e15;
for(ll j = 0; j <= k; j ++){
cv = min(cv, dis[en][j]);
}
return cv == 1e15 ? -1 : cv;
}
// void _() {
// }
// signed main() {
// ll tm = clock();
// cin.tie(0)->sync_with_stdio(0);
// ll t = 1;
// // cin >> t;
// for(ll tt = 1; tt <= t; tt ++) _();
// cerr << "\n\033[1;31mTime: \033[1;30m" \
// << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n";
// }
