#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=100000;
vector<vector<pair<int,double>>> adj;
bool alc[MAXN], vis[MAXN];
void dfs(int u, const int& ban){
alc[u]=true;
for(auto [v,t]:adj[u]){
if(v==ban)continue;
if(!alc[v]){
dfs(v, ban);
}
}
}
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) {
memset(alc, 0, sizeof(alc));
adj.clear();
adj.resize(N);
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]});
}
dfs(0,H);
set<pair<double,int>> q;
q.insert({0,0});
double op1=1e18, op2=1e18;
while(!q.empty()){
auto [d,u]=*q.begin();
q.erase(q.begin());
vis[u]=true;
if(u==H){
op1=d;
break;
}
for(auto [v,t]:adj[u]){
if(!vis[v]){
q.insert({d+t,v});
}
}
}
q.clear();
q.insert({0,H});
memset(vis, 0, sizeof(vis));
vector<double> dist(N, 1e18);
while(!q.empty()){
auto [d,u]=*q.begin();
q.erase(q.begin());
vis[u]=true;
if(arr[u]==0){
op2=d;
break;
}
for(auto [v,t]:adj[u]){
if(alc[v]&&!vis[v]){
q.insert({d+t,v});
}
}
}
memset(vis, 0, sizeof(vis));
return min(op1, op2);
}
