#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN=1e5+1;
vector<pair<ll,ll>>grafo[MAXN];
ll ar[MAXN], h;
bool vis[MAXN];
vector<ll>pos;
struct nod
{
ll nodo, k;
double dis;
bool operator<(nod x)
const {
return dis>x.dis;
}
};
bool ap=0;
void dfs(ll nod)
{
if(nod==h)
{
ap=1;
return;
}
vis[nod]=1;
if(ar[nod]==0||nod==0)
pos.pb(nod);
for(auto k:grafo[nod])
if(vis[k.fr]==0)
dfs(k.fr);
}
void init(ll N)
{
pos.resize(0);
for(ll i=0; i<N; i++)
{
grafo[i].resize(0);
vis[i]=0;
}
ap=0;
}
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) {
init(N);
ll i;
h=H;
for(i=0; i<N; i++)
ar[i]=arr[i];
for(i=0; i<M; i++)
{
grafo[x[i]].pb({y[i],c[i]});
grafo[y[i]].pb({x[i],c[i]});
}
priority_queue<nod>pq;
nod v;
vector<vector<double>>dist(N,vector<double>(K+1,1e14));
dfs(0);
if(ap==0)
return -1;
for(auto k:pos)
{
v.k=0;
v.nodo=k;
v.dis=0;
dist[k][0]=0;
pq.push(v);
}
while(pq.size())
{
v=pq.top();
pq.pop();
if(v.nodo==H)
continue;
if(v.dis!=dist[v.nodo][v.k])
continue;
for(auto k:grafo[v.nodo])
{
if(ar[k.fr]==0)
continue;
nod nV;
nV.nodo=k.fr;
nV.k=v.k+1;
nV.dis=v.dis/2+k.se;
if(ar[v.nodo]==2&&v.k+1<=K&&nV.dis<dist[k.fr][nV.k])
{
dist[k.fr][nV.k]=nV.dis;
pq.push(nV);
}
nV.k--;
nV.dis=v.dis+k.se;
if(nV.dis<dist[k.fr][nV.k])
{
dist[k.fr][nV.k]=nV.dis;
pq.push(nV);
}
}
}
double mi=dist[H][0];
for(i=1; i<=K; i++)
mi=min(mi,dist[H][i]);
return mi;
}
