#include<bits/stdc++.h>
using namespace std;
const int MAXK=71;
const int MAXN=(1e5+7)*MAXK;
const int MAXM=(1e5+7)*MAXK;
int NNN;
struct edge{
 int nxt,v,w;
}e[MAXM<<1];
int h[MAXN],cnt;
inline void add_edge(int u,int v,int w){
 e[++cnt].nxt=h[u],e[cnt].v=v,e[cnt].w=w;
 h[u]=cnt;
}
bool vis[MAXN/MAXK];
inline void dfs(int u,int H){
 vis[u]=1;
 for(int i=h[u];i;i=e[i].nxt){
  int v=e[i].v;
  if(vis[v]||v>NNN||u==H) continue;
  dfs(v,H);
 }
}
struct node{
 double dis;
 int pos;
 friend bool operator <(node x,node y){
  if((x.pos-1)/NNN>(y.pos-1)/NNN) return 1;
  if((x.pos-1)/NNN<(y.pos-1)/NNN) return 0;
  return x.dis>y.dis;
 }
}tmp;
double dis[MAXN];
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){
 cnt=0; K=min(K,70); NNN=N; H++;
 for(int i=1;i<=N*K+N;i++) h[i]=0;
 for(int i=1;i<=N*K+N;i++) dis[i]=1e17;
 for(int i=1;i<=N;i++) vis[i]=0;
 for(int i=0;i<M;i++){
  x[i]++,y[i]++;
  for(int j=0;j<=K;j++){
   add_edge(j*N+x[i],j*N+y[i],c[i]);
   add_edge(j*N+y[i],j*N+x[i],c[i]);
  }
 }
 for(int i=1;i<=N;i++){
  if(arr[i-1]!=2) continue;
  for(int j=0;j<K;j++){
  	add_edge(j*N+i,j*N+N+i,-1);
  }
 }
 dfs(1,H);
 if(!vis[H]) return -1;
 priority_queue<node> q;
 for(int i=1;i<=N;i++){
  if((vis[i]&&arr[i-1]==0)||i==1){
   tmp.dis=0,tmp.pos=i;q.push(tmp);
   dis[i]=0;
  }
 }
 while(!q.empty()){
  tmp=q.top(); q.pop(); int u=tmp.pos;
  if(dis[u]!=tmp.dis) continue;
  if((u-1)%N+1==H) continue;
  for(int i=h[u];i;i=e[i].nxt){
   int v=e[i].v,w=e[i].w;
   if(w==-1){
   	if(dis[u]/2<dis[v]){
   	 dis[v]=dis[u]/2;
	 tmp.dis=dis[v],tmp.pos=v;
	 q.push(tmp);	
	}
   }
   else if(dis[u]+w<dis[v]){
   	dis[v]=dis[u]+w;
   	tmp.dis=dis[v],tmp.pos=v;
   	q.push(tmp);
   }
  }
 }
 double ans=1e17;
 for(int i=0;i<=K;i++)
  ans=min(ans,dis[i*N+H]);
 //cout<<dis[1]<<" "<<dis[2]<<" "<<dis[3]<<"\n";
 return ans;
}