#include "minecraft.h"
#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct edge
{
    ll ver, dist;
    edge(){};
    edge(ll _ver, ll _dist){ver=_ver; dist=_dist;};
    bool operator <(const edge &e)const
    {
        return dist>e.dist;
    }
};

vector<edge>v[200001];
unsigned ll dp[100001];

void dijkstra(int s)
{
    memset(dp, -1, sizeof(dp));
    priority_queue<edge>pq;
    pq.push({s, 0});
    while(pq.size()>0)
    {
        edge e=pq.top();
        pq.pop();
        if(e.dist<=dp[e.ver])
        {

            for(int i=0; i<v[e.ver].size(); i++)
            {
                edge nb=v[e.ver][i];
                //cout<<e.ver<<' '<<e.dist<<' '<<nb.ver<<' '<<nb.dist<<' '<<dp[nb.ver]<<endl;
                if(e.dist+nb.dist<=dp[nb.ver])
                {
                    //cout<<e.ver<<' '<<nb.ver<<endl;
                    nb.dist+=e.dist;
                    dp[nb.ver]=nb.dist;
                    pq.push(nb);
                }
            }
        }
    }
}

std::vector<int> portals(int N, int K)
{
    vector<int>ans;
    for(int i=1; i<=N; i++)
    {
        if(find_portals(i, i)==1)ans.push_back(i);
    }
    return ans;
}

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)
{
    for(int i=0; i<paths.size(); i++)
    {
        pair<int, pair<int, int>>t=paths[i];
        v[t.second.first].push_back({t.second.second, t.first});
        v[t.second.second].push_back({t.second.first, t.first});
    }
    ll mn=LLONG_MAX;
    pair<ll, ll>ans;
    for(int i=0; i<portals.size(); i++)
    {
        dijkstra(portals[i]);
        //cout<<dp[2]<<' '<<dp[4]<<' '<<dp[7]<<' '<<dp[10]<<endl;
        for(int j=0; j<fortresses.size(); j++)
        {
            if(dp[fortresses[j]]<mn)
            {
                ans.first=portals[i];
                ans.second=fortresses[j];
                mn=dp[fortresses[j]];
            }
        }
    }
    return ans;
}

std::pair<int, int> find_end_portal(int L)
{
    int e=L, w=L, n=L, s=L;
    string st;
    pair<int, int>q;
    int l=1, r=L;
    while(l<r)
    {
        int m=l+(r-l)/2;
        st=throw_eye({m, 1});
        if(st=="NONE")return {m, 1};
        if(st=="NE")l=m+1;
        else if(st=="NW")r=m-1;
        else if(st=="N")
        {
            r=m;
            break;
        }
    }
    q.first=r;
    int row=r;
    l=1; r=L;
    while(l<r)
    {
        int m=l+(r-l)/2;
        st=throw_eye({row, m});
        if(st=="NONE")return {row, m};
        if(st=="N")l=m+1;
        else if(st=="S")r=m-1;
    }
    q.second=r;
    return q;
}
