#include "cyberland.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"
// ==========================(debug)============================================================================================== //
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif
void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
// ==========================(debug)============================================================================================== //
ll n,m,tp,tp2,res,cnt,sum,tptp,ans,q,k;
const ll mx = 2e5+5;
const ll mod = 1e9+7;
// ==========================(MOD)=============================================================================================== //
ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }
// ==========================(MOD)=============================================================================================== //
bool f = false;
vector<pi> adj[mx];
double dis[mx][105];
vector<int> node;
bool vis[mx];
double rip[105];
priority_queue<pair<double,pi>,vector<pair<double,pi>>,greater<pair<double,pi>>> pq;
typedef struct Disjoint_Set_Union{
ll parent[mx];
ll siz[mx];
ll src;ll dest;
void init(ll k){
fip(0,k+2){
parent[i] = i;
siz[i] = 1;
}
}
ll find(ll u){
return parent[u] == u ? u : parent[u] = find(parent[u]);
}
bool unite(ll u,ll v){
src = find(u);
dest = find(v);
if(src==dest)
return 1;
if(siz[src] < siz[dest])
swap(src,dest);
parent[dest] = src;
siz[src] += siz[dest];
return 0;
}
}DSU;
DSU dsu;
void dfs(ll u){
vis[u] = 1;
if(u==tp){
f = 0;
return ;
}
fx(adj[u]) {
if(!vis[x.ff])
dfs(x.ff);
}
return;
}
void emptify(){
while(pq.size()){
pq.pop();
}
return;
}
void printer(){
priority_queue<pair<double,pi>,vector<pair<double,pi>>,greater<pair<double,pi>>> pq2 = pq;
cout<<"start - > ";
while(pq2.size()){
debug(pq2.top());
pq2.pop();
}
cout<<" end."<<nli;
return;
}
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;
tp = H;
node.clear();
dsu.init(n);
k = min(100,K);
rip[0] = 1;
fip(1,k+1)
rip[i] = rip[i-1] / 2;
node = arr;
fip(0,n+2){
adj[i].clear();
fjp(0,105)
dis[i][j] = 1e18+5;
vis[i] = 0;
}
emptify();
fip(0,m){
if(x[i] != tp && tp != y[i])
dsu.unite(x[i],y[i]);
adj[x[i]].push_back({y[i],c[i]});
adj[y[i]].push_back({x[i],c[i]});
}
f = 1;
node[0] = 0;
dfs(0);
if(f)
return -1;
pq.push({0,{tp,k}});
double na = -1;
cout<<setprecision(6);
dis[tp][k] = 0;
while(pq.size()){
auto it = pq.top();
pq.pop();
if(dis[it.ss.ff][it.ss.ss] < it.ff)
continue;
if(node[it.ss.ff]==0){
na = it.ff;
break;
}
fx(adj[it.ss.ff]){
if(dsu.find(0) != dsu.find(x.ff))
continue;
if(it.ff + x.ss * rip[k-it.ss.ss] < dis[x.ff][it.ss.ss]){
dis[x.ff][it.ss.ss] = it.ff + x.ss * rip[k-it.ss.ss];
pq.push({dis[x.ff][it.ss.ss],{x.ff,it.ss.ss}});
}
if(node[it.ss.ff] == 2 && it.ss.ss >= 1){
if(it.ff + x.ss * rip[k-it.ss.ss+1] < dis[x.ff][it.ss.ss-1]){
dis[x.ff][it.ss.ss-1] = it.ff + x.ss * rip[k-it.ss.ss+1];
pq.push({dis[x.ff][it.ss.ss-1],{x.ff,it.ss.ss-1}});
}
}
}
}
return na;
}
// int main(){
// ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("input1.txt", "r", stdin);
// freopen("output1.txt", "w", stdout);
// freopen("error1.txt", "w", stderr);
// #endif // ONLINE_JUDGE
// test{
// int N,M,K;
// cin>>N>>M>>K;
// vector<int> x(M);
// vector<int> y(M);
// vector<int> c(M);
// vector<int> arr(N);
// int H;
// cin>>H;
// fip(0,N){
// cin>>arr[i];
// }
// fip(0,M){
// cin>>x[i]>>y[i]>>c[i];
// }
// // for(auto y : x)
// // cout<<y<< " ";
// // cout<<nli;
// // cout<<" OK";
// cout<<solve(N,M,K,H,x,y,c,arr)<<nli;
// }
// cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
// return 0;
// }
