#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
double eps=1/(1e9);
vector<pair<int,double>> adj[N];
double dist[N];
bool vis[N];
int spe[N];
double mn=2e14;
double dyk(int s,int e)
{
for(int j=0;j<n;j++)
dist[j]=1e14+1;
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;
dist[s]=0;
pq.push({dist[s],s});
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.second==e)
return tp.first;
if((tp.first-dist[tp.second])<=eps)
{
int v=tp.second;
for(auto [u,w]:adj[v])
{
if((dist[v]+w)<dist[u])
{
dist[u]=dist[v]+w;
pq.push({dist[u],u});
}
}
}
}
return -1;
}
void dfs(int x,double dis=0)
{
if(spe[x]==0)
dis=0;
mn=min(mn,dis+dist[x]);
// cout<<"For "<<x<<' '<<dis<<' '<<dist[x]<<endl;
vis[x]=1;
for(auto [u,w]:adj[x])
{
if(!vis[u])
{
dfs(u,dis+w);
}
}
}
double solve(int NP, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
n=NP;
// DONT FORGET TO CLEAR THE THINGS YOU USED
for(int i=0;i<n;i++)
{
adj[i].clear();
spe[i]=arr[i];
}
bool all_one=1;
for(auto i:arr)
all_one&=(i==1);
for(int j=0;j<m;j++)
{
adj[x[j]].push_back({y[j],c[j]});
adj[y[j]].push_back({x[j],c[j]});
}
bool two=0;
for(auto i:arr)
two|=(i==2);
if(all_one)
{
return dyk(0,h);
}
else if(!two)
{
dyk(h,-1);
// compute distance from h
adj[h].clear();
// Reachibility from 0
mn=2e14;
dfs(0);
return mn;
}
return -1;
}
