#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
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<int, int>>> 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]);
}
vector<ll> dist(N, 1e18+1);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> dijkstra;
dijkstra.emplace(0, 0);
while(!dijkstra.empty()) {
auto [d, u] = dijkstra.top();
dijkstra.pop();
if(d >= dist[u]) continue;
dist[u] = d;
for(auto [v, cv]: adj[u]) {
dijkstra.emplace(d + cv, v);
}
}
if(dist[H] == 1e8+1) return -1;
return dist[H];
}
