#include <bits/stdc++.h>
using namespace std;
long double const EPS=1e-6;
struct per{
int nod,dist;
};
struct len{
int nod;
long double dist;
};
class cmp{
public:
bool operator()(len a,len b){
return a.dist>b.dist;
}
};
double solve(int N,int M,int K,int H,vector<int>x,vector<int>y,vector<int>c,vector<int>arr){
vector<bool>viz;
viz.resize(N+5,0);
vector<vector<per>>G;
G.resize(N+5);
int i;
int sz=x.size();
for(i=0;i<sz;++i){
G[x[i]].push_back({y[i],c[i]});
G[y[i]].push_back({x[i],c[i]});
}
queue<int>q;
q.push(0);
viz[0]=1;
viz[H]=1;
while(!q.empty()){
int curr=q.front();
q.pop();
for(auto vec : G[curr])
if(!viz[vec.nod]){
viz[vec.nod]=1;
q.push(vec.nod);
}
}
vector<long double>before;
before.resize(N+5,-1);
priority_queue<len,vector<len>,cmp>pq;
for(i=0;i<N;++i)
if(arr[i]==0 && viz[i]==1)
pq.push({i,0});
pq.push({0,0});
while(!pq.empty()){
len curr=pq.top();
pq.pop();
int nod=curr.nod;
long double dist=curr.dist;
if(before[nod]!=-1)
continue;
before[nod]=dist;
for(auto vec : G[nod]){
int nd=vec.nod;
long double dst=vec.dist;
pq.push({nd,dist+dst});
}
}
vector<long double>after;
after.resize(N+5,-1);
for(i=0;i<N;++i)
if(arr[i]==2 && viz[i]==1){
int j;
long double dist=before[i];
for(j=1;j<=K;++j)
dist/=2;
pq.push({i,dist});
}
while(!pq.empty()){
len curr=pq.top();
pq.pop();
int nod=curr.nod;
long double dist=curr.dist;
if(after[nod]!=-1)
continue;
after[nod]=dist;
for(auto vec : G[nod]){
int nd=vec.nod;
long double dst=vec.dist;
pq.push({nd,dist+dst});
}
}
if(before[H]==-1)
return -1;
if(after[H]==-1)
return before[H];
if(before[H]<after[H])
return before[H];
else
return after[H];
}
