#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
ll dis[2][N];
vector<pair<int, ll>> adj[N];
void dijkstra(int x, int idx) {
priority_queue<pair<ll, int>> pq;
pq.push(make_pair(-0, x));
while (!pq.empty()) {
ll d = -pq.top().first;
int y = pq.top().second;
pq.pop();
if (dis[idx][y] != -1) continue;
dis[idx][y] = d;
for (auto& [z, d2] : adj[y]) {
if (dis[idx][z] != -1) continue;
pq.push(make_pair(-(d+d2), z));
}
}
}
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++) {
adj[i].clear();
}
for (int i = 0; i < m; i++) {
adj[x[i]].push_back(make_pair(y[i], c[i]));
adj[y[i]].push_back(make_pair(x[i], c[i]));
}
for (int i = 0; i < n; i++) {
dis[0][i] = dis[1][i] = -1;
}
dijkstra(0, 0);
dijkstra(h, 1);/*
for (int i = 0; i < n; i++) {
cerr << dis[0][i] << " " << dis[1][i] << endl;
}*/
ll ans = dis[0][h];
for (int i = 0; i < n; i++) {
//assert(arr[i] >= 0 && arr[i] < 2);
if (!k || arr[i] || dis[0][i] == -1 || dis[1][i] == -1) continue;
ans = min(ans, dis[1][i]);
}
return ans;
}
