#include "cyberland.h"
#include <bits/stdc++.h>
// #include "stub.cpp"
using namespace std;
const int N=1e5+10;
const long double inf=1e18;
int n,arr[N];
vector<pair<int,long long>> adj[N];
long double dist[N],MS=-1;
long double dyk(int s,int e)
{
for(int j=0;j<n;j++)
dist[j]=inf;
priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,int>>> pq;
dist[s]=0;
pq.push({dist[s],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 double dyk_comb(int e)
{
dyk(0,e);
priority_queue<pair<long double,int>,vector<pair<long double,int>>,greater<pair<long double,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;
if(arr[v]==2)
{
dist[v]/=2;
tp.first/=2;
}
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=n-1;i>=0;i--)
{
if(AS[i]==2)
{
if(k==0)
{
AS[i]=1;
}
else
k--;
}
}
for(int i=0;i<n;i++)
{
arr[i]=AS[i];
adj[i].clear();
}
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]});
}
return dyk_comb(h);
}
