#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define EPS 1e-9
#define INF 1023456789
#define LINF 1023456789123456789
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define disc(x) x.resize(unique(all(x))-x.begin())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef vector<ii> vii;
typedef pair<double,int> di;
typedef tuple<double,int,int> dii;
#define maxn 100005
#define maxk 75
double dist[maxn][maxk];
vector<ii> AL[maxn];
double solve(int N,int M,int K,int H,vi x,vi y,vi c,vi arr){
K=min(K,70);
priority_queue<di,vector<di>,greater<di>> pq;
for(int i=0;i<N;++i){
for(int j=0;j<=K;++j)dist[i][j]=LINF;
AL[i].clear();
}
dist[0][0]=0;
for(int i=0;i<M;++i){
AL[x[i]].pb({y[i],c[i]});
AL[y[i]].pb({x[i],c[i]});
}
for(int k=0;k<=K;++k){
for(int i=0;i<N;++i){
if(dist[i][k]!=LINF)pq.push({dist[i][k],i});
}
while(!pq.empty()){
auto[d,u]=pq.top();pq.pop();
if(abs(dist[u][k]-d)>EPS||u==H)continue;
for(auto[v,w]:AL[u]){
if(arr[v]==0&&dist[v][k]>0){
dist[v][k]=0;
pq.push({0,v});
continue;
}
if(arr[u]==2&&k<K&&dist[v][k+1]>d/2+w){
dist[v][k+1]=min(dist[v][k+1],d/2+w);
}
if(dist[v][k]>d+w){
dist[v][k]=d+w;
pq.push({dist[v][k],v});
}
}
}
}
double ans=LINF;
for(int i=0;i<=K;++i)ans=min(ans,dist[H][i]);
return ans==LINF?-1:ans;
}
