#pragma GCC optimize("O3,unroll-loops")
#ifndef Local
#include "cyberland.h"
#endif
#include <bits/stdc++.h>
using namespace std;
const int lim=1e5+10;
const double inf=2e30;
using pii=pair<int,int>;
using pdi=pair<double,int>;
vector<pii> v[lim];
bool vis[lim];
int n,m,k,h;
void dfs(int node){
vis[node]=1;
if(node==h)return;
for(auto [f,s]:v[node]){
if(!vis[f]){
dfs(f);
}
}
}
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) {
n=N,m=M,k=min(K,100),h=H;
for(int i=0;i<m;i++){
v[x[i]].push_back({y[i],c[i]});
v[y[i]].push_back({x[i],c[i]});
}
dfs(0);
double *dist[2];
dist[0]=new double[n];
dist[1]=new double[n];
//for(int i=0;i<n;i++)cerr<<vis[i]<<"\n";
for(int i=0;i<n;i++){
dist[0][i]=(arr[i]||!vis[i])?inf:0;
}
priority_queue<pdi,vector<pdi>,greater<pdi>>pq;
dist[0][0]=0;
pq.push({0,0});
//else cerr<<arr[0]<<"\n";
double ans=inf;
for(int rp=0;rp<min(k,100);rp++){
/*
for(int i=0;i<n;i++){
cerr<<dist[0][i]<<" ";
}cerr<<"\n";
*/
for(int i=0;i<n;i++){
dist[1][i]=arr[i]?inf:0;
}
while(pq.size()){
auto nn=pq.top();
pq.pop();
double cost=nn.first;
int node=nn.second;
/*
cerr<<node<<" "<<cost<<" visited\n";
cerr<<cost<<" "<<dist[0][node]<<"\n";
*/
if(cost!=dist[0][node]||node==h)continue;
//cerr<<"ok\n";
if(arr[node]==2){
dist[1][node]=min(dist[1][node],cost/2);
}
for(auto j:v[node]){
if(cost+j.second<dist[0][j.first]){
//cerr<<node<<" inserted "<<j.first<<" "<<cost+j.second<<"\n";
dist[0][j.first]=cost+j.second;
//cerr<<dist[0][j.first]<<" "<<cost+j.second<<"\n";
pq.push({cost+j.second,j.first});
}//else cerr<<cost<<" "<<j.second<<" "<<dist[0][j.first]<<"\n";
}
}
/*
for(int i=0;i<n;i++){
cerr<<dist[0][i]<<" ";
}cerr<<"\n";
for(int i=0;i<n;i++){
cerr<<dist[1][i]<<" ";
}cerr<<"\n";
cerr<<h<<"\n";
*/
for(int i=0;i<n;i++){
pq.push({dist[1][i],i});
}
ans=min(ans,dist[0][h]);
ans=min(ans,dist[1][h]);
//cerr<<ans<<"\n";
swap(dist[0],dist[1]);
}
/*
for(int i=0;i<n;i++){
cerr<<dist[0][i]<<" ";
}cerr<<"\n";
*/
return ans;
}
#ifdef Local
int main(){
cout<<solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1})<<"\n";
}
#endif
