#include "cyberland.h"

#include <iostream>
#include <algorithm>
#include <queue>

typedef long long ll;
typedef double lf;

using namespace std;

const int MAXN = 1e5 + 10, MAXM = 7e6 + 10;

int n, m, d, ed;
int tp[MAXN];
int id[MAXN], idx[MAXN], cnt;
lf ans;

struct Edge
{
    int v, nxt, w;
}e[MAXN << 1];
int head[MAXN], tot;
inline void AddEdge(int u, int v, int w)
{
    if (u != ed) e[++tot] = Edge{v, head[u], w}, head[u] = tot;
    if (v != ed) e[++tot] = Edge{u, head[v], w}, head[v] = tot;
}

bool vis[MAXN];
void DFS(int u)
{
    vis[u] = 1;
    for (int i = head[u]; ~i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == ed) vis[ed] = 1;
        else if (!vis[v]) DFS(v);
    }
}

lf dis[MAXM]; bool avl[MAXM];
priority_queue < pair <lf, int>, vector < pair <lf, int> >, greater < pair <lf, int> > > q;
lf solve(int N, int M, int K, int H, vector <int> FR, vector <int> TO, vector <int> CST, vector <int> ARR)
{
    n = N, m = M, d = min(K, 30), ed = H + 1;
    for (int i = 1; i <= n; i++)
    {
        tp[i] = ARR[i - 1];
        head[i] = -1, vis[i] = id[i] = idx[i] = 0;
    }
    tot = -1;
    for (int i = 1; i <= m; i++)
        AddEdge(FR[i - 1] + 1, TO[i - 1] + 1, CST[i - 1]);
    DFS(1);
    if (!vis[ed]) return -1;
    cnt = 0;
    for (int i = 1; i <= n; i++)
        if (tp[i] == 2 && vis[i]) id[i] = ++cnt, idx[cnt] = i;
    int T = n * (d + 1), ED = T + cnt * d;
    for (int i = 1; i <= ED; i++) dis[i] = 1e18;
    ans = 1e18;
    for (int i = 1; i <= n; i++)
        if (i == 1 || (tp[i] == 0 && vis[i])) dis[i] = 0, q.push(make_pair(dis[i], i));
    while (!q.empty())
    {
        int u = q.top().second; q.pop();
        if (avl[u]) continue;
        // cerr << u << " " << dis[u] << "\n";
        avl[u] = 1;
        if (u <= T)
        {
            int ly = (u - 1) / n, p = u - ly * n, np = T + id[p] + ly * cnt;
            for (int i = head[p]; ~i; i = e[i].nxt)
            {
                int v = e[i].v + ly * n;
                if (dis[v] > dis[u] + e[i].w)
                    dis[v] = dis[u] + e[i].w, q.push(make_pair(dis[v], v));
            }
            if (ly != d && tp[p] == 2 && dis[np] > dis[u] / 2)
                dis[np] = dis[u] / 2, q.push(make_pair(dis[np], np));
            if (p == ed) ans = min(ans, dis[u]);
        }
        else
        {
            int ly = (u - T - 1) / cnt, p = idx[u - T - ly * cnt];
            for (int i = head[p]; ~i; i = e[i].nxt)
            {
                int v = e[i].v + (ly + 1) * n;
                if (dis[v] > dis[u] + e[i].w)
                    dis[v] = dis[u] + e[i].w, q.push(make_pair(dis[v], v));
            }
        }
    }
    return ans;
}