#include<iostream>
#include<vector>
#include<queue>
#include"minecraft.h"
using namespace std;
vector<pair<long long, int>> adj[100001];
priority_queue<pair<pair<long long, int>, int>, vector<pair<pair<long long, int>, int>>, less<>> djik;
long long dist[100001];
int from[100001];
void djikstra()
{
    while(!djik.empty())
    {
        int cur = djik.top().first.second, beg = djik.top().second;
        long long w = djik.top().first.first;
        djik.pop();
        if(w >= dist[cur]) continue;
        dist[cur] = w;
        from[cur] = beg;
        for(auto [we, next] : adj[cur])
        {
            if(dist[next] > w + we)
            {
                djik.push({{w+we, next}, beg});
            }
        }
    }
}
int find(int c, int N)
{
    int l = c, r = N;
    while(l < r)
    {
        int m = (l+r)/2;
        if(find_portals(l, m)) r = m;
        else l = m+1;
    }
    return l;
}
vector<int> portals(int N, int K)
{
    vector<int> ans;
    int l = 1, found = 0;
    while(found!=K)
    {
        ans.push_back(find(l, N));
        l = ans.back()+1;
        found++;
    }
    return ans;
}
pair<int, int> minimal_danger(int N, vector<pair<int, pair<int, int>>> paths, vector<int> portals, vector<int> fortresses)
{
    for(auto [w, endings] : paths)
    {
        adj[endings.first].push_back({(long long)w, endings.second});
        adj[endings.second].push_back({(long long)w, endings.first});
    }
    for(int i = 1; i <= N; i++) dist[i] = 1e16;
    for(int x : portals) djik.push({{0LL, x}, x});
    for(int x : portals) from[x] = x;
    djikstra();
    int best = fortresses[0], bestfrom = from[fortresses[0]];
    for(int x : fortresses)
    {
        if(dist[x] < dist[best])
        {
            best = x;
            bestfrom = from[x];
        }
    }
    return {bestfrom, best};
}
pair<int, int> find_end_portal(int L)
{
    return {0, 0};
}