#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;
const int kmax = 120;
const long long oo = LLONG_MAX;
int n,m,k,f;
int tip[nmax + 5];
double d[nmax + 5][kmax + 5];
bool sel[nmax + 5][kmax + 5];
vector<pair<int,int>> G[nmax + 5];
vector<int> l;
typedef pair<pair<int,double>,int> pi;
void add_zero(int nod)
{
sel[nod][0] = true;
if(tip[nod]==0)
{
l.push_back(nod);
}
if(nod==f)
{
return;
}
for(auto it : G[nod])
{
if(sel[it.first][0])
{
continue;
}
add_zero(it.first);
}
}
void Dijkstra()
{
priority_queue <pi,vector<pi>,greater<pi>> h;
for(int i=0;i<n;i++)
{
for(int p=0;p<=min(kmax,k);p++)
{
d[i][p] = oo;
sel[i][p] = false;
}
}
d[0][0] = 0;
h.push({{0,0},0});
l.clear();
add_zero(0);
if(!sel[f][0])
{
d[f][0] = -1;
return;
}
for(int i=0;i<n;i++)
{
sel[i][0] = false;
}
for(auto it : l)
{
d[it][0] = 0;
h.push({{0,0},it});
}
while(!h.empty())
{
while(!h.empty() && sel[h.top().second][h.top().first.first])
{
h.pop();
}
if(h.empty())
{
return;
}
int nod = h.top().second;
int nr = h.top().first.first;
h.pop();
sel[nod][nr] = true;
if(nod==f)
{
continue;
}
for(auto it : G[nod])
{
double new_t = d[nod][nr] + it.second;
if(tip[it.first]==0)
{
continue;
}
if(new_t < d[it.first][nr])
{
d[it.first][nr] = new_t;
h.push({{nr,d[it.first][nr]},it.first});
}
if(tip[it.first]==2 && nr < min(kmax,k))
{
if(new_t * 0.5 < d[it.first][nr + 1])
{
d[it.first][nr+1] = new_t * 0.5;
h.push({{nr+1,d[it.first][nr+1]},it.first});
}
}
}
}
}
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
n = N, m = M, k = K, f = H;
for(int i=0;i<m;i++)
{
G[x[i]].push_back({y[i],c[i]});
G[y[i]].push_back({x[i],c[i]});
}
for(int i=0;i<n;i++)
{
tip[i] = arr[i];
}
Dijkstra();
for(int i=0;i<n;i++)
{
G[i].clear();
}
double rez = oo;
for(int p=0;p<=min(kmax,k);p++)
{
rez = min(rez, d[f][p]);
}
return rez;
}
