#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
double sub_2_5(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<double> dp(N, (double)(1e15));
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]});
}
dp[0] = 0;
pq.push({0,dp[0]});
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id] < u.w) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id] + v.second < dp[v.first]){
dp[v.first] = dp[u.id] + v.second;
pq.push({v.first, dp[v.first]});
}
}
}
if(dp[H] == (double)(1e15)) dp[H] = -1;
return dp[H];
}
double sub_3_6(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
struct ii{
int id;
double w;
};
struct cmp{
bool operator () (ii A, ii B){
return A.w > B.w;
}
};
priority_queue<ii, vector<ii>, cmp> pq;
vector<double> dp(N, (double)(1e15));
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]});
}
dp[0] = 0;
pq.push({0,dp[0]});
vector<bool> vis(N,false);
queue<int> Q;
Q.push(0);
vis[0] = true;
while(Q.size()){
int u = Q.front();
Q.pop();
for(pair<int,int> v: G[u]){
if(vis[v.first] == true || v.first == H) continue;
vis[v.first] = true;
Q.push(v.first);
}
}
for(int i=1;i<N;i++){
if(arr[i] == 0 && vis[i] == true){
dp[i] = 0;
pq.push({i,dp[i]});
}
}
while(pq.size()){
ii u = pq.top();
pq.pop();
if(dp[u.id] < u.w) continue;
for(pair<int,int> v: G[u.id]){
if(dp[u.id] + v.second < dp[v.first]){
dp[v.first] = dp[u.id] + v.second;
pq.push({v.first, dp[v.first]});
}
}
}
if(dp[H] == (double)(1e15)) dp[H] = -1;
return dp[H];
}
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){
int check_sub_2_5 = 0;
for(int i=0;i<N;i++) check_sub_2_5 += (arr[i] == 1);
if(check_sub_2_5 == N) return sub_2_5(N,M,K,H,x,y,c,arr);
int check_sub_3_6 = 0;
for(int i=0;i<N;i++) check_sub_3_6 += (arr[i] != 2);
if(check_sub_3_6 == N) return sub_3_6(N,M,K,H,x,y,c,arr);
return -1;
}
