#include "cyberland.h"
#ifdef VANWIJ
#define DBG 1
#else
#include"bits/stdc++.h"
#define DBG 0
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}
#define float double
const float INF = 1e18;
const float E = 1e-8;
const int N = 1e5+5;
const int K = 69;
int n, m, k, tar;
V<pii> adj[N];
// {-moves, -dist, node}
priority_queue<tuple<int,float,int>> pq;
float d[N][K];
void relax(int mov,float dist,int node){
if(d[node][mov] <= dist) return;
d[node][mov] = dist;
pq.push({-mov,-dist,node});
}
double solve(int _n,int _m,int _k,int _tar,V<int> mx,V<int> my,V<int> mc,V<int> arr){
n = _n; m = _m; k = _k; tar = _tar;
k = min(k, K-2);
rep(i,0,n){
adj[i].clear();
rep(j,0,K){
d[i][j] = INF;
}
}
rep(i,0,m){
adj[mx[i]].push_back({my[i], mc[i]});
adj[my[i]].push_back({mx[i], mc[i]});
}
float ans = INF;
relax(0,0,0);
while(!pq.empty()){
auto[mov,dist,x] = pq.top(); pq.pop();
mov *= -1; dist *= -1;
if(abs(d[x][mov]-dist) > E) continue;
assert(0<=x && x<n);
assert(0<=mov && mov<=k);
if(x==tar){
ans = min(ans, dist);
continue;
}
if(arr[x]==0){
relax(mov, 0, x);
}
for(auto[y,w] : adj[x]){
relax(mov, dist+w, y);
if(mov<k && arr[x]==2){
relax(mov+1, dist/2+w, y);
}
}
}
if(ans > N*1e9) return -1;
return ans;
}
