#include "cyberland.h"
#include <bits/stdc++.h>
// #include "stub.cpp"
using namespace std;
const int N=1e5+10;
const long long inf=1e16;
int n,arr[N];
vector<pair<int,long long>> adj[N];
long long dist[N],MS=-1;
long long dyk(int s,int e)
{
for(int j=0;j<n;j++)
dist[j]=inf;
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
dist[s]=0;
pq.push({0,s});
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.second==e) // this is cz we dont go other side of h
continue;
if(tp.first==dist[tp.second])
{
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});
}
}
}
}
// cout<<"DY from "<<s<<endl;
// for(int pp=0;pp<n;pp++)
// {
// cout<<dist[pp]<<' ';
// }
// cout<<endl;
return ((dist[e]==inf)?MS:dist[e]);
}
long long dyk_comb(int e)
{
dyk(0,e);
priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>> pq;
for(int j=0;j<n;j++)
{
if(dist[j]!=inf and (j==0 or arr[j]==0))
{
dist[j]=0;
pq.push({0,j});
}
else
dist[j]=inf;
}
while(pq.size())
{
auto tp=pq.top();
pq.pop();
if(tp.first==dist[tp.second])
{
if(tp.second==e)
{
continue;
}
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 ((dist[e]==inf)?MS:dist[e]);
}
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();
}
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;
}
