#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,arr[N];
double eps=1/(1e9);
vector<pair<int,double>> adj[N];
double dist[N];
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({0,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;
}
double dyk_comb(int e)
{
dyk(0,e);
vector<int> acd;
priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> pq;
for(int j=0;j<n;j++)
{
if(dist[j]<(1e14+1) and arr[j]==0)
{
acd.push_back(j);
dist[j]=0;
pq.push({0,j});
}
else
dist[j]=1e14+1;
}
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;
}
double solve(int NP, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> AS) {
n=NP;
// DONT FORGET TO CLEAR THE THINGS YOU USED
for(int i=0;i<n;i++)
{
arr[i]=AS[i];
adj[i].clear();
}
arr[0]=0;
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]});
}
if(all_one)
{
return dyk(0,h);
}
else{
return dyk_comb(h);
}
return -1;
}
