#include <bits/stdc++.h>
#define vi vector <int>
#define pdi pair<double, pair<int,int>>
using namespace std;
using ll = long long;
const int N = 1e5 + 5, mod = 1e9 + 7;
const double inf = 1e18;
bool vis[N];
vi g[N], luu;
int n, m, k, h, x[N], y[N], c[N], arr[N], trace[N];
double dist[N];
void dfs(int u) {
if (arr[u] == 0) luu.push_back(u);
vis[u] = 1; //cout << u << '\n';
for (int id : g[u]) {
//cout << id << '\n';
int v = x[id]; //cout << v << '\n';
if (v == u) v = y[id]; //cout << v << '\n';
if (!vis[v]) dfs(v);
}
}
double solve(int N, int M, int K, int H, vi X, vi Y, vi C, vi ARR) {
n = N;
m = M;
k = K;
h = H;
luu.clear();
fill(vis, vis + n, 0);
for (int i = 0; i < n; ++i) g[i].clear(), arr[i] = ARR[i];
for (int i = 0; i < m; ++i) {
x[i] = X[i];
y[i] = Y[i];
c[i] = C[i];
g[x[i]].push_back(i);
g[y[i]].push_back(i); //cout << x[i] << ' ' << y[i] << ' ' << c[i] << '\n';
}
dfs(0);
if (!vis[h]) return -1;
priority_queue <pdi,vector<pdi>,greater<pdi>> pq;
fill(trace, trace + n, 0);
fill(dist, dist + n, inf);
dist[0] = 0;
pq.push({0, {0, 0}});
for (int v : luu) {
dist[v] = 0;
pq.push({0, {v, 0}});
}
while (!pq.empty()) {
double D = pq.top().first;
int u = pq.top().second.first;
int lap = pq.top().second.second;
pq.pop();
if (D != dist[u] && lap > trace[u]) continue;
for (int id : g[u]) {
int v = x[id];
if (v == u) v = y[id];
double W = D + c[id];
if (W < dist[v] || (W == dist[v] && trace[v] > lap)) {
trace[v] = lap;
dist[v] = W;
pq.push({W, {v, lap}});
}
if (arr[v] == 2) {
W /= 2;
if (W < dist[v] || (W == dist[v] && trace[v] > lap + 1)) {
dist[v] = W;
trace[v] = lap + 1;
pq.push({W, {v, lap + 1}});
}
}
}
}
return dist[h];
}
