#ifdef LOCAL
#include "stub.cpp"
#endif
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,sse4,bmi2,popcnt")
#define int long long
#define iint signed
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)((x).size()))
#define SQ(x) ((x)*(x))
#define pii pair<int,int>
#define pipii pair<int,pii>
#define ppi pair<pii,int>
#define Graph vector<vector<int>>
#define Graphw vector<vector<pii>>
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define md(x) (((x)%(mod)+(mod))%(mod))
#define MD(x,M) (((x)%(M)+(M))%(M))
#define ld double
#define pdd pair<ld,ld>
template<typename S> void chmin(S &x,S y) { x=min(x,y); }
template<typename S> void chmax(S &x,S y) { x=max(x,y); }
#define addmod(x,y) x=((x+(y))%mod)
#define Vi vector<int>
#define Vpii vector<pii>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) {cout<<(#x)<<":";for(auto allen:(x)) cout<<allen<<" ";cout<<" size="<<(x).size()<<endl;}
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& os,pair<T1,T2> p) { return os<<'{'<<p.f<<','<<p.s<<'}'; }
template<typename T1,typename T2>
istream& operator>>(istream& os,pair<T1,T2> &p) { return os>>p.f>>p.s; }
template<typename S>
ostream& operator<<(ostream& os,vector<S> p) { for(auto allen:p) os<<allen<<' ';return os<<'\n'; }
template<typename S>
istream& operator>>(istream& os,vector<S> &p) { for(auto &allen:p) os>>allen;return os; }
template<typename T1,typename T2>
pair<T1,T2> operator+(pair<T1,T2> p1,pair<T1,T2> p2) { return pair<T1,T2>(p1.f+p2.f,p1.s+p2.s); }
const int mod=998244353;
const int maxn=1e5+5;
const int maxv=1e6+5;
const int inf=1ll<<60;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int rd(int l,int r) {
// return uniform_int_distribution<int>(l,r)(rng);
// }
double solve(iint N, iint M, iint K, iint H, std::vector<iint> x, std::vector<iint> y, std::vector<iint> c, std::vector<iint> arr) {
int n=N,m=M,k=K,h=H;
Graphw g(n);
Vi a(n);
REP(i,m) {
g[x[i]].pb({y[i],c[i]});
g[y[i]].pb({x[i],c[i]});
}
REP(i,n) a[i]=arr[i];
/////
Vi can(n,0);
{
queue<int> q;
q.push(0);
while(SZ(q)) {
int u=q.front();
q.pop();
if(can[u]) continue;
can[u]=1;
if(u==h) continue;
for(auto [v,w]:g[u]) {
q.push(v);
}
}
}
if(can[h]==0) return -1;
vector<int> dis0(n,inf);
{
auto &dis=dis0;
Vi vis(n);
#define pdi pair<int,int>
priority_queue<pdi,vector<pdi>,greater<pdi>> pq;
REP(i,n) if(can[i]&&(i==0||a[i]==0)) {
dis[i]=0;
pq.push({dis[i],i});
}
while(SZ(pq)) {
int u=pq.top().s;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto [v,w]:g[u]) {
if(dis[v]>dis[u]+w) {
dis[v]=dis[u]+w;
pq.push({dis[v],v});
}
}
}
}
int lg=min(120ll,k+1);
vector<vector<ld>> dis(lg,vector<ld>(n,inf));
#define pip pair<ld,pii>
priority_queue<pip,vector<pip>,greater<pip>> pq;
pq.push({0,{0,h}});
dis[0][h]=0;
auto val=[&](ld x,int y) ->ld {
REP(i,y) x=x/2;
return x;
};
vector<Vi> vis(lg,Vi(n));
while(SZ(pq)) {
auto [x,u]=pq.top().s;
pq.pop();
if(vis[x][u]) continue;
vis[x][u]=1;
for(auto [v,w]:g[u]) {
if(v==h) continue;
if(dis[x][v]>dis[x][u]+val(w,x)) {
dis[x][v]=dis[x][u]+val(w,x);
pq.push({dis[x][v],{x,v}});
}
if(x<lg-1&&a[v]==2) {
if(dis[x+1][v]>dis[x][u]+val(w,x)) {
dis[x+1][v]=dis[x][u]+val(w,x);
pq.push({dis[x+1][v],{x+1,v}});
}
}
}
}
ld an=inf;
REP(i,lg) REP(j,n) if(dis0[j]!=inf) chmin(an,val((ld)dis0[j],i)+dis[i][j]);
// oparr(dis)oparr(dis0)
return an;
}
