#include "cyberland.h"
#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b or a == -1) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
struct edge {
int u, v, w;
edge () {};
edge (int _u, int _v, int _w) {
u = _u, v = _v, w = _w;
}
} e[N];
int n, m, k, h, ar[N];
vec<pair<int, int>> g[N];
#define ld double
const ld esp = (ld)1e-9;
namespace SUB1 {
const int K = 70;
ld dis[N][K];
ld sol() {
FOR(i, 0, n - 1)
FOR(j, 0, k) dis[i][j] = -1;
dis[0][0] = 0;
#define T pair<ld, ii>
priority_queue<T, vec<T>, greater<T>> pq;
pq.push(_mp(0, _mp(0, 0)));
while (!pq.empty()) {
auto x = pq.top(); pq.pop();
int u = x.se.fi;
int t = x.se.se;
// cout<<u<<' '<<t<<' '<<dis[u][t]<<nl;
if (u == h) continue ;
if (abs(x.fi - dis[u][t]) > esp) continue ;
for(auto j : g[u]) {
int v = j.fi;
// khong dung
if (ar[v] == 0) {
if (dis[v][0]==-1){
dis[v][0]=0;
pq.push(_mp(0, _mp(v,0)));
}
}else if(ar[v]==1){
if (mini(dis[v][t], dis[u][t] + j.se)){
pq.push(_mp(dis[v][t], _mp(v, t)));
}
}else{
if (mini(dis[v][t], dis[u][t] + j.se)){
pq.push(_mp(dis[v][t], _mp(v, t)));
}
//arr[v]=2 ->
if (t + 1 <= k and mini(dis[v][t+1], (dis[u][t] + j.se)/2.0)){
pq.push(_mp(dis[v][t+1], _mp(v, t+1)));
}
}
}
}
ld ans=-1;
FOR(i,0,k){
if (dis[h][i]!=-1){
// cout << h << ' ' << i << ' ' << dis[h][i] << nl;
mini(ans, dis[h][i]);
}
}
// cout << fixed << setprecision(6) << "ans: " << ans << nl;
return ans;
}
};
ld solve(int N, int M, int K, int H,
vector<int> x, vector<int> y,
vector<int> c, vector<int> arr) {
n = N, m = M, k = K, h = H;
FOR(i, 0, n - 1) ar[i] = arr[i];
FOR(i, 0, n - 1) g[i].clear();
for(int i = 0; i < m; ++i) {
e[i] = edge(x[i], y[i], c[i]);
g[x[i]].emplace_back(y[i], c[i]);
g[y[i]].emplace_back(x[i], c[i]);
}
return SUB1::sol();
return 0;
}
/* Let the river flows naturally */
