#include "minecraft.h"
#include <bits/stdc++.h>
#include <vector>

const int MAXM = 2e5 + 2;

using namespace std;

void Solve_Portals(int l, int r, int k, vector<int>& result)
{
    if (k == 0) return;
    if(r - l + 1 == k)
    {
        for(int i = l; i <= r; i++)
            result.push_back(i);
        return;
    }
    if (l == r)
    {
        result.push_back(l);
        return;
    }

    int mid = l + (r - l) / 2;
    int left_k = find_portals(l, mid);

    Solve_Portals(l, mid, left_k, result);
    Solve_Portals(mid + 1, r, k - left_k, result);
}

vector<int> portals(int N, int K)
{
    vector<int> result;
    Solve_Portals(1, N, K, result);
    return result;
}

vector<pair<int, int>> v[MAXM];

pair<int, int> minimal_danger(int N, vector<pair<int, pair<int, int>>> paths, vector<int> portals, vector<int> fortresses)
{
    int a, b, c;
    for(auto st:paths)
    {
        tie(a, b) = st.second;
        c = st.first;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }

    const long long INF = 2e18;
    vector<long long> tim(N + 1, INF);
    vector<int> origin(N + 1, -1);

    priority_queue<pair<int, int>> pq;
    for (int p : portals)
    {
        tim[p] = 0;
        origin[p] = p;
        pq.push({0, p});
    }

    long long x, k;
    while(!pq.empty()){
        tie(k, x) = pq.top();
        pq.pop();
        k = -k;
        if(tim[x] < k)
            continue;

        for(auto [to, cost]:v[x]){
            if(k + cost >= tim[to])
                continue;
            origin[to] = origin[x];
            tim[to] = k + cost;
            pq.push({-tim[to], to});
        }
    }

    long long min_t = INF;
    int best_por = -1;
    int best_fort = -1;

    for (int f : fortresses) {
        if (tim[f] < min_t) {
            min_t = tim[f];
            best_por = origin[f];
            best_fort = f;
        }
    }

    return {best_por, best_fort};
}

std::pair<int, int> find_end_portal(int L)
{
    return {1, 1};
}
