#include "cyberland.h"
#include <vector>
#include <iostream>
#include <limits.h>
#include <queue>
#include <algorithm>
typedef long long ll;
typedef double lld;
const lld MAX_DIST=10000000000000000000000000.0;
using namespace std;
int n,m,k,h;
vector<pair<int,lld>>nodes[100000];
lld dist[100000];
lld old_dist[100000];
bool vis[100000];
void dfs(int node){
if(vis[node])
return;
vis[node]=true;
if(node==h)
return;
for(pair<int,lld>ne:nodes[node]){
dfs(ne.first);
}
}
double 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(int i=0;i<n;i++){
nodes[i].clear();
dist[i]=MAX_DIST;
vis[i]=false;
}
for(int i=0;i<m;i++){
nodes[x[i]].emplace_back(y[i],c[i]);
nodes[y[i]].emplace_back(x[i],c[i]);
}
dfs(0);
dist[0]=0;
queue<int>q;
q.push(0);
if(!vis[h])
return -1;
for(int i=0;i<n;i++){
if(arr[i]==0&&vis[i]){
dist[i]=0;
q.push(i);
}
}
k=min(100,k);
for(int j=0;j<k;j++){
while(!q.empty()){
int curr=q.front();
q.pop();
if(curr==h)
continue;
for(pair<int,lld>ne:nodes[curr]){
lld new_dist=dist[curr]+ne.second;
if(new_dist<dist[ne.first]){
dist[ne.first]=new_dist;
q.push(ne.first);
}
}
}
for(int i=0;i<n;i++)
old_dist[i]=dist[i];
for(int i=0;i<n;i++){
if(arr[i]==2&&vis[i]){
for(pair<int,lld>ne:nodes[i]){
lld new_dist=old_dist[i]/2.0+ne.second;
if(new_dist<dist[ne.first]){
dist[ne.first]=new_dist;
q.push(ne.first);
}
}
}
}
if(q.empty())
break;
}
while(!q.empty()){
int curr=q.front();
q.pop();
if(curr==h)
continue;
for(pair<int,lld>ne:nodes[curr]){
lld new_dist=dist[curr]+ne.second;
if(new_dist<dist[ne.first]){
dist[ne.first]=new_dist;
q.push(ne.first);
}
}
}
return dist[h];
}
