//chockolateman
#include<bits/stdc++.h>
// #include "cyberland.h"
using namespace std;
const double INF = 1e15;
int n,T,status[100005];
double dist[100005][105];
bool visited[100005][105];
vector<pair<int,int>> adj[100005];
void Dijkstra()
{
for(int i = 0 ; i < n ; i++)
for(int k = 0 ; k <= 100 ; k++)
{
dist[i][k] = INF;
visited[i][k] = false;
}
for(int k = 0 ; k <= 100 ; k++)
{
visited[T][k] = true;
dist[0][k] = 0;
}
priority_queue<pair<double,pair<int,int>>> q;
q.push({0,{0,0}});
while(!q.empty())
{
int v = q.top().second.first;
int k = q.top().second.second;
q.pop();
if(visited[v][k])
continue;
visited[v][k] = true;
for(auto e : adj[v])
{
int u = e.first;
int w = e.second;
double cur = dist[v][k] + w;
if(status[u]==0)
cur = 0;
if(cur < dist[u][k])
{
dist[u][k] = cur;
q.push({-cur,{u,k}});
}
if(status[u]==2 && k < 100)
{
cur /= 2.00;
if(cur < dist[u][k+1])
{
dist[u][k+1] = cur;
q.push({-cur,{u,k+1}});
}
}
}
}
}
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;
T = H;
for(int i = 0 ; i < M ; i++)
{
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
for(int i = 0 ; i < N ; i++)
status[i] = arr[i];
Dijkstra();
double ret = INF;
for(int k = 0 ; k <= min(K,100) ; k++)
ret = min(ret,dist[H][k]);
if(ret >= INF-5)
ret = -1;
for(int i = 0 ; i < N ; i++)
adj[i].clear();
return ret;
}
