#include <bits/stdc++.h>
#include "minecraft.h"
using namespace std;

vector <int> v;

void f(int l=0, int r=0, int k=0) {
    if (l+k==r) {
        for (int i=l;i<r;i+=1) v.push_back(i);
        return;
    }
    int m=(l+r)/2;
    int k1=find_portals(l, m-1);
    if (k1) f(l, m, k1);
    if (k-k1) f(m, r, k-k1);
}

vector<int> portals(int n, int k) {
    f(1,  n+1, k);
    return v;
}


std::pair<int, int> minimal_danger(int n, std::vector<std::pair<int, std::pair<int, int>>> paths, std::vector<int> portals, std::vector<int> fortresses) {
    bool m[n]{};
    bool used[n]{};
    for (int e:fortresses) m[e]=1;
    vector <pair <int, int>> g[n];
    for (pair<int, pair<int, int>> e:paths) {
        g[e.second.first].push_back({e.second.second, e.first});
        g[e.second.second].push_back({e.second.first, e.first});
    }
    priority_queue <pair <int, pair <int, int>>, vector <pair <int, pair <int, int>>>, greater <pair <int, pair <int, int>>>> q;
    for (int e:portals) q.push({0, {e, e}});
    while (!q.empty()) {
        pair <int, pair <int, int>> p=q.top();
        q.pop();
        if (used[p.second.second]==0) {
            used[p.second.second]=1;
            if (m[p.second.second]) {
                return p.second;
            }
            for (pair <int, int> e:g[p.second.second]) {
                if (used[e.first]==0) {
                    q.push({p.first+e.second, {p.second.first, e.first}});
                }
            }
        }
    }
    return make_pair(0, 0);
}

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