#include "cyberland.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define ld long double
#pragma GCC optimize("Ofast")
const int mxN = 1e5 + 1;
vector<pii> adj[mxN];
short special[mxN];
int n, k, h;
bool cango[mxN];
void FindConnected() {
queue<int> q;
q.push(0); cango[0] = true;
while (!q.empty()) {
int cur = q.front(); q.pop();
if (cur == h) continue;
for (pii &v : adj[cur]) {
if (!cango[v.ff]) {
q.push(v.ff);
cango[v.ff] = true;
}
}
}
}
const int mxK = 70;
double dist[mxN][mxK];
priority_queue<pair<double, pii>, vector<pair<double, pii>>, greater<pair<double, pii>>> pq;
const double INF = 1e18, EPS = 1e-8;
void FindAnswer() {
while (!pq.empty()) pq.pop();
for (int i = 0; i < n; i++) {
for (int j = 0; j <= min(k, mxK - 1); j++) {
dist[i][j] = INF;
}
}
dist[0][0] = 0;
pq.push({0, {0, 0}});
for (int i = 0; i < n; i++) {
if (cango[i] && special[i] == 0) {
dist[i][0] = 0;
pq.push({0, {i, 0}});
}
}
while (!pq.empty()) {
pair<double, pii> cur = pq.top();
pq.pop();
// if (cur.ss.ss <= 3) {
// cerr << "DIJK " << cur.ff << ' ' << cur.ss.ff << ' ' << cur.ss.ss << endl;
// }
if (cur.ff > dist[cur.ss.ff][cur.ss.ss]) continue;
if (cur.ss.ff == h) continue;
double ncur;
for (pii &v : adj[cur.ss.ff]) {
ncur = cur.ff + v.ss;
if (ncur < dist[v.ff][cur.ss.ss]) {
dist[v.ff][cur.ss.ss] = ncur;
pq.push({ncur, {v.ff, cur.ss.ss}});
}
if (special[v.ff] == 2 && cur.ss.ss + 1 < mxK) {
ncur /= 2;
if (ncur < dist[v.ff][cur.ss.ss + 1]) {
dist[v.ff][cur.ss.ss + 1] = ncur;
pq.push({ncur, {v.ff, cur.ss.ss + 1}});
}
}
}
}
}
double solve(int N, int M, int K, int H, vector<int> X, vector<int> Y, vector<int> C, vector<int> arr) {
n = N; k = K; h = H;
for (int i = 0; i < n; i++) {
adj[i].clear();
cango[i] = false;
}
for (int i = 0; i < M; i++) {
adj[X[i]].pb({Y[i], C[i]});
adj[Y[i]].pb({X[i], C[i]});
}
for (int i = 0; i < n; i++) {
special[i] = arr[i];
}
// assert(special[0] == 1 && special[h] == 1);
FindConnected();
if (!cango[h]) return -1;
// cerr << setprecision(1) << fixed;
FindAnswer();
// cerr << "DEBUG:\n";
// for (int i = 0; i < n; i++) {
// cerr << "NODE " << i << ": ";
// for (int j = 0; j < 3; j++) cerr << dist[i][j] << ' ';
// cerr << endl;
// }
double res = 1e18;
for (int i = 0; i <= min(k, mxK - 1); i++) {
res = min(res, dist[h][i]);
}
return res;
}
