#include "cyberland.h"
#include<bits/stdc++.h>
#define pb push_back
#define ll long long int
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long int, long long int>>
#define pqpll priority_queue<pair<long long int, long long int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define mii map<int,int>
#define mll map<long long int, long long int>
#define mivi map<int,vector<int>>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
using namespace std;
const int mxn = 100005;
vpll adj[mxn];
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) {
f0r(i, M){
adj[x[i]].pb({y[i], c[i]});
adj[y[i]].pb({x[i], c[i]});
}
priority_queue<pair<ll,ll>>q;
vb vis(N, false);
vb vis2(N, false);
vll dist1(N, 4e18);
vll dist2(N, 4e18);
q.push({0, 0});
vis[0] = 1;
dist1[0] = 0;
while(!q.empty()){
pair<ll,ll>cur = q.top();
q.pop();
ll c = cur.second;
for(auto u : adj[c]){
if(!vis[u.first]){
ll w = u.second;
vis[u.first] = 1;
dist1[u.first] = dist1[c] + w;
q.push({-dist1[u.first], u.first});
}
}
}
q.push({0, H});
vis2[H] = 1;
dist2[H] = 0;
while(!q.empty()){
pair<ll,ll>cur = q.top();
q.pop();
ll c = cur.second;
for(auto u : adj[c]){
if(!vis2[u.first]){
ll w = u.second;
vis2[u.first] = 1;
dist2[u.first] = dist2[c] + w;
q.push({-dist2[u.first], u.first});
}
}
}
if(!vis[H])return -1;
else{
ll mn = 4e18;
f0r(i, N){
if(arr[i] == 0 && vis[i])mn = min(mn, dist2[i]);
}
if(mn == 4e18)return dist2[0];
else return mn;
}
}
