#include <bits/stdc++.h>
#include "cyberland.h"
using namespace std;
using ll = long long;

#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#define dbgarr(...)
#endif


//subtask 2 and 5
//
const ll INF = 0x3f3f3f3f3f3f3f3f;
vector<vector<pair<int, ll>>> adj;

void dijkstra(int s, vector<ll> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);

    d[s] = 0;
    set<pair<int, int>> q;
    q.insert({0, s});
    while (!q.empty()) {
        int v = q.begin()->second;
        q.erase(q.begin());

        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                q.erase({d[to], to});
                d[to] = d[v] + len;
                p[to] = v;
                q.insert({d[to], to});
            }
        }
    }
}

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) {
    adj.clear();
    adj.resize(N);
    for(int i=0; i<M; i++){
        int l = x[i], r=y[i], cost = c[i];
        adj[l].push_back({r, cost});
        adj[r].push_back({l, cost});
    }
    vector<ll> d(N);
    vector<int> p(N);
    dijkstra(0,d,p);
    return (d[H]==INF ? -1 : d[H]); // if 0 and H is not connectdd
}