#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
double const INF = 1e15;
int const N = 1e5;
vector<vector<pair<int, int>>> adj(N);
vector<double> dist(N);
vector<double> dist2(N);
vector<bool> processed(N);
priority_queue<pair<double, int>> q;
double answer = INF;
void dijkstra(int number, int target)
{
for (int j=0; j<number; j++) {processed[j] = false;}
dist[0] = 0;
for (int j = 0; j<number; j++) if (dist[j] < INF) q.push({-dist[j], j});
while (!q.empty())
{
int a = q.top().second; q.pop();
if (processed[a]) continue;
processed[a] = true;
for (auto u : adj[a])
{
int b = u.first, w = u.second;
if (dist[a]+w < dist[b])
{
dist[b] = dist[a]+w;
q.push({-dist[b],b});
}
}
}
answer = min(answer, dist[target]);
}
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr)
{
for (int i=0; i<m; i++)
{
int v = x[i]; int u = y[i]; int w = c[i];
adj[v].push_back({u, w});
adj[u].push_back({v, w});
}
for (int i=0; i<n; i++) {dist[i] = INF;}
dijkstra(n, h);
if (dist[h] == INF) {return -1;}
for (int i=0; i<n; i++) {if (dist[i] != INF) dist[i] = (arr[i] ? INF : 0);}
k = min(k, 65);
for (int i=1; i<=k; i++)
{
dijkstra(n, h);
for (int j=0; j<n; j++) {dist2[j] = INF;}
for (int j=0; j<n; j++)
{
if (arr[j] == 2) {
for (auto p: adj[j]) {
int u = p.first; int w = p.second;
dist2[u] = min(dist2[u], dist[j]/2+w);
}
}
}
for (int j=0; j<n; j++) {dist[j] = dist2[j];}
}
return answer;
}
