//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];
bool reached[100005];
vector<pair<int,int>> adj[100005];
void dfs(int v)
{
if(reached[v])
return;
reached[v] = true;
for(auto e : adj[v])
{
int u = e.first;
dfs(u);
}
}
void Dijkstra()
{
for(int i = 0 ; i < n ; i++)
for(int k = 0 ; k <= 100 ; k++)
{
dist[i][k] = INF;
visited[i][k] = false;
}
priority_queue<pair<pair<int,double>,int>> q;
dist[0][0] = 0;
q.push({{0,0},0});
for(int v = 1 ; v < n ; v++)
if(reached[v] && status[v]==0)
{
dist[v][0] = 0;
q.push({{0,0},v});
}
for(int k = 0 ; k <= 100 ; k++)
visited[T][k] = true;
while(!q.empty())
{
int v = q.top().second;
int k = q.top().first.first;
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(cur < dist[u][k])
{
dist[u][k] = cur;
q.push({{-k,-dist[u][k]},u});
}
if(status[u]==2 && k < 100)
{
cur /= 2.00;
if(cur < dist[u][k+1])
{
dist[u][k+1] = cur;
q.push({{-(k+1),-cur},u});
}
}
}
}
}
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];
dfs(0);
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();
reached[i] = false;
}
return ret;
}
