#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>>> g(N);
for (int i = 0; i<M; i++) {
g[x[i]].push_back({y[i], c[i]});
g[y[i]].push_back({x[i], c[i]});
}
vector<long long> dist(N, 1e18);
dist[0] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
pq.push({0, 0});
while(pq.size()){
auto [d, cur] = pq.top();
pq.pop();
if (dist[cur]!=d) continue;
for (auto [e, w]: g[cur]){
if (dist[e]>d+w){
dist[e] = d+w;
pq.push({dist[e], e});
}
}
}
if (dist[H]==1e18) return -1;
return dist[H];
}
// int main() {
// cout<<solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
// {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19});
// }
