/*
written by sim_ple
*/
#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
#define int long long
#define N 500005
#define itn int
#define all(x) x.begin() , x.end()
#define INF 1e9
double dp[N][30];
vector<pair<int , int>> path[N];
int vis[N];
void dfs(int node , int error){
if(vis[node]) return;
vis[node] = 1;
for(auto i : path[node]){
if(error == i.first) continue;
dfs(i.first , error);
}
}
double solve(int n , int m , int k , int h , vector<int> x , vector<int> y , vector<int> c , vector<int> arr){
for(int i = 0; i < n; i++){
path[i].clear();
vis[i] = 0;
for(int j = 0; j <= 30; j++){
dp[i][j] = INF;
}
}
for(int i = 0; i < m; i++){
path[x[i]].push_back({y[i] , c[i]});
path[y[i]].push_back({x[i] , c[i]});
}
int ans = INF;
priority_queue<tuple<double , int , int> , vector<tuple<double , int , int>> , greater<tuple<double , int , int>>> q;
q.push({0 , h , 0});
dp[h][0] = 0;
while(!q.empty()){
double a;
int b , c;
tie(a , b , c) = q.top();
q.pop();
if(dp[b][c] < a) continue;
if(!arr[b] or !b){
for(int i = 0; i <= k; i++){
ans = min((double)ans , dp[b][i]);
}
}
dp[b][c] = a;
for(auto i : path[b]){
if(vis[i.first] and i.first != h){
if(dp[i.first][c] > dp[b][c] + (i.second / (1 << c))){
dp[i.first][c] = dp[b][c] + (i.second / (1 << c));
q.push({dp[i.first][c] , i.first , c});
}
if(arr[i.first] == 2 and c < k and dp[i.first][c + 1] > dp[b][c] + (i.second / (1 << c))){
dp[i.first][c + 1] = dp[b][c] + (i.second / (1 << c));
q.push({dp[i.first][c + 1] , i.first , c + 1});
}
}
}
}
if(ans == INF){
return -1;
}
return ans;
}
// void solve1(){
// int n , m , k , idx;
// cin >> n >> m >> k >> idx;
// vector<int> x(m + 1) , y(m + 1) , c(m + 1);
// for(int i = 0; i < m; i++){
// cin >> x[i];
// }
// for(int i = 0; i < m; i++){
// cin >> y[i];
// }
// for(int i = 0; i < m; i++){
// cin >> c[i];
// }
// vector<int> arr(n + 1);
// for(int i = 0; i < n; i++){
// cin >> arr[i];
// }
// dfs(0 , idx);
// cout << solve(n , m , k , idx , x , y , c , arr) << endl;
// }
// int32_t main() {
// ios::sync_with_stdio(0); cin.tie(0);
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
// int t = 1;
// //cin >> t;
// while(t--) solve1();
// return 0;
// }
