#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define in(v) for(auto &elem:v){ cin>>elem; }
#define out(v) for(auto elem:v){ cout<<elem<<" "; } cout<<endl;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
struct Edge{
int to, w;
};
struct Node{
double d;
int u, op;
bool operator<(const Node& other) const{
return d > other.d;
}
};
double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> cc, vector<int> arr) {
k = min(k, 67);
vector<vector<Edge>> adj(n);
vector<int> deg(n, 0);
for(int i = 0; i < m; i++){
deg[x[i]]++;
deg[y[i]]++;
}
for(int i = 0; i < n; i++) adj[i].reserve(deg[i]);
for(int i = 0; i < m; i++){
adj[x[i]].push_back({y[i], cc[i]});
adj[y[i]].push_back({x[i], cc[i]});
}
const double INF = 1e100;
int W = k + 1;
vector<double> dist(n * W, INF);
auto id = [&](int u, int op){
return u * W + op;
};
priority_queue<Node> pq;
dist[id(0, 0)] = 0;
pq.push({0, 0, 0});
double ans = INF;
while(!pq.empty()){
Node cur = pq.top();
pq.pop();
int u = cur.u, op = cur.op;
double c = cur.d;
if(c != dist[id(u, op)]) continue;
if(u == h){
ans = min(ans, c);
continue;
}
for(const auto &e : adj[u]){
int v = e.to;
int w = e.w;
double ch1 = c + w;
if(arr[v] == 0) ch1 = 0;
int idx1 = id(v, op);
if(ch1 < dist[idx1]){
dist[idx1] = ch1;
pq.push({ch1, v, op});
}
if(op < k && arr[u] == 2){
double ch2 = c / 2.0 + w;
if(arr[v] == 0) ch2 = 0;
int idx2 = id(v, op + 1);
if(ch2 < dist[idx2]){
dist[idx2] = ch2;
pq.push({ch2, v, op + 1});
}
}
}
}
return ans >= INF / 2 ? -1 : ans;
}
/*int main(){
int n, m, k, h;
cin>>n>>m>>k>>h;
vector<int> x(m), y(m), c(m), arr(n);
for(ll i = 0; i<m; i++){
cin>>x[i]>>y[i]>>c[i];
}
for(ll i = 0; i<n; i++){
cin>>arr[i];
}
cout<<solve(n, m, k, h, x, y, c, arr);
}*/
