#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using std::vector;
using std::pair;
using std::priority_queue;
vector<vector<pair<int, int>>> adj;
int dijkstra(int s, int h) {
int n = adj.size();
vector<int> dist(n, 1e9);
vector<bool> vis(n, false);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> pq;
pq.push({0, s});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto &p: adj[u]) {
int v = p.first;
int w = p.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist[h];
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
adj.assign(n, {});
for (int i = 0; i<m; ++i) {
int u = x[i], v = y[i], w = c[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int res = dijkstra(0, h);
return (res == 1e9 ? -1 : res);
// return dist[h];
}
// int main() {
// int res = solve(3, 1, {-1, 0, 0}, {{1, 2}});
// cout << res << '\n';
// }
