#define tungtungsteno 0;
#define IPERSUSSONE M
#define we i
#define quaqua std;
#define tastiera Y
#define topolino long,
#define biscottiniii pair
#define BASTAAAA P
#define blurb X,
#define AFS_PROBLEMA_SEGRETO M;
#define piccionebuco for
#define toad vector
#define paperago ,
#define giaaaaaaaaaaaaaaaaa mincammino
#define dfs if
#define chescemochesonoio !pq.empty
#define treap_di_dsu :
#define settantatrequarantadue u,
#define sus auto
#define sixseven u
#define disoifj void
#define bfs N
#define qwertyuiopasdfghjklzxcvbnm &
#define nonsocosastofacendo priority_queue
#define YUPPIIIII 0,
#define blublurblablubbluss 1e18;
#define hehehe N,
#define super_perdita int
#define sunnov8238pm M,
#define catalan w
#define CIAISSIMO d,
#define camicie continue;
#define POV_DEI_BISCOTTI while
#define efs d
#define z 0
#define iorewivfj pq.pop
#define vfwcskljvkpwfsd Y,
#define piccionemagico w;
#define qualcunomistaguardando N;
#define gnamgnam using
#define scotch pq.emplace
#define timmy_loves_gambling 1;
#define easter_egg 1e17
#define camice pq;
#define seisette &i:
#define tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema main
#define aria D
#define ohnoooo X
#define ciao v
#define cfs long
#define scioccherellinooo cin
#define papera .push_back
#define pkhoviintoleoiimadaicirendiamocontodovesiamofinitiHAHAHAHA namespace
#define ifohncm int,
#define YAYYYYY ;
#define pikapikaCHUUUUUUCHUHCUSIDVJAO G
#define mannagginerellina pq.top
#define dijkstra P,
#include <bits/stdc++.h>
gnamgnam pkhoviintoleoiimadaicirendiamocontodovesiamofinitiHAHAHAHA quaqua 
 
#define ll long long
#include <cassert>
 
disoifj giaaaaaaaaaaaaaaaaa(super_perdita hehehe super_perdita sunnov8238pm toad<super_perdita> blurb toad<super_perdita> vfwcskljvkpwfsd toad<super_perdita> dijkstra toad<cfs cfs>qwertyuiopasdfghjklzxcvbnm aria) { 
    nonsocosastofacendo<biscottiniii<cfs topolino cfs cfs>> camice 
    toad<toad<biscottiniii<ifohncm super_perdita>>> pikapikaCHUUUUUUCHUHCUSIDVJAO(bfs)YAYYYYY 
 
    piccionebuco(super_perdita we = tungtungsteno we < qualcunomistaguardando we ++) { 
        aria[we] = blublurblablubbluss 
    } 
 
    aria[z] = tungtungsteno 
 
    piccionebuco(super_perdita we = tungtungsteno we < AFS_PROBLEMA_SEGRETO we++) { 
        pikapikaCHUUUUUUCHUHCUSIDVJAO[ohnoooo[we]]papera({tastiera[we]paperago BASTAAAA[we]})YAYYYYY 
    } 
 
    scotch(YUPPIIIII z)YAYYYYY 
 
    POV_DEI_BISCOTTI(chescemochesonoio()) { 
        sus [CIAISSIMO ciao] = mannagginerellina()YAYYYYY 
        iorewivfj()YAYYYYY 
 
        dfs(-efs > aria[ciao]) camicie 
 
        piccionebuco(sus [settantatrequarantadue catalan]treap_di_dsu pikapikaCHUUUUUUCHUHCUSIDVJAO[ciao]) { 
            dfs(aria[sixseven] > -efs + catalan) { 
                aria[sixseven] = -efs + piccionemagico 
                scotch(-aria[sixseven]paperago sixseven)YAYYYYY 
            } 
        } 
    } 
 
    piccionebuco(sus seisette aria) dfs(we >= easter_egg) we = -timmy_loves_gambling 
} 
 
 
#ifndef EVAL
super_perdita tuttisannocheilmuchhialberoelastrutturadatidefinitivacapacedirisolverequalsiasiproblema() { 
    super_perdita hehehe AFS_PROBLEMA_SEGRETO 
    scioccherellinooo >> bfs >> AFS_PROBLEMA_SEGRETO 
 
    toad<super_perdita> ohnoooo(IPERSUSSONE)paperago tastiera(IPERSUSSONE)paperago BASTAAAA(IPERSUSSONE)YAYYYYY 
    toad<cfs cfs> aria(bfs)YAYYYYY 
 
    piccionebuco (super_perdita we = tungtungsteno we < AFS_PROBLEMA_SEGRETO we++) { 
        scioccherellinooo >> ohnoooo[we] >> tastiera[we] >> BASTAAAA[we]YAYYYYY 
    } 
 
    giaaaaaaaaaaaaaaaaa(hehehe sunnov8238pm blurb vfwcskljvkpwfsd dijkstra aria)YAYYYYY 
 
 
} 
#endif