#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<bool> isReachable;
void dfs(ll v, vector<vector<pair<ll,ll>>>& adj, ll H) {
if(v == H) return;
for(pair<ll,ll> u : adj[v]) {
if(!isReachable[u.first]) {
isReachable[u.first] = true;
dfs(u.first, adj, H);
}
}
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int>y, std::vector<int> c, std::vector<int> arr) {
vector<vector<pair<ll,ll>>> adj(N);
for (int i = 0; i < M; i++) {
adj[x[i]].emplace_back(y[i], c[i]);
adj[y[i]].emplace_back(x[i], c[i]);
}
isReachable.clear();
isReachable.resize(N);
dfs(0, adj, H);
isReachable[0] = true;
if(!isReachable[H]) return -1;
K = min(K, 60);
priority_queue<tuple<double,ll,ll>, vector<tuple<double,ll,ll>>, greater<>> pq;
vector<vector<ll>> dist(N + 10, vector<ll>(K + 10, 1e16));
pq.emplace(0, 0, 0);
dist[0][0] = 0;
for(int i = 1; i < arr.size(); i++) {
if(arr[i] == 0) {
pq.emplace(0, i, 0);
dist[i][0] = 0;
}
}
while(!pq.empty()) {
ll curDistance = get<0>(pq.top());
ll curNode = get<1>(pq.top());
ll curK = get<2>(pq.top());
pq.pop();
if(dist[curNode][curK] < curDistance) continue;
for(auto u : adj[curNode]) {
ll newDistance = curDistance + u.second;
if(newDistance < dist[u.first][curK]) {
dist[u.first][curK] = newDistance;
pq.emplace(newDistance, u.first, curK);
}
if(arr[curNode] == 2 && curK < K) {
newDistance /= 2;
if(newDistance < dist[u.first][curK + 1]) {
dist[u.first][curK + 1] = newDistance;
}
}
}
}
ll ans = 1e16;
for (int i = 0; i <= K; ++i) {
ans = min(ans, dist[H][i]);
}
return ans;
}
