#include <bits/stdc++.h>
#define L(i, m, n) for(int i(m);i < n;i++)
#define pb push_back
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define in(x) cin >> x
#define SZ(X) int(X.size())
#define clr(A, V) L(i, 0, 111) A[i]=V
#define inf 999999
#define ff first
#define ss second
#define RF(X) freopen(X, "r", stdin)
#define WF(X) freopen(X, "w", stdout)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<int, string> pis;
typedef vector<string> vs;
typedef pair<pair<int, int>, pair<int, int > > piiii;

const int INF=1e9;
vi dist(10009, INF); /**Don't forget to check nodes number and memset each test**/
void Dijkstra(int &V, vector <vpii> &AdjList, int &s){
    dist[s] = 0; /** INF = 1B to avoid overflow**/
    priority_queue< pii, vector<pii>, greater<pii> > pq; /**parameters**/
    pq.push(pii(0, s));
    while (!pq.empty()){
        pii front = pq.top(); pq.pop(); int d=front.ff,u=front.ss;
        if (d > dist[u]) continue; /** Lazy Deletion **/
        L(j,0,SZ(AdjList[u])){
            pii v = AdjList[u][j];/**first vertex number, weight second**/
            if (dist[u]+v.ss < dist[v.ff]){
                dist[v.ff] = dist[u] + v.ss; /** relax operation**/
                pq.push(pii(dist[v.ff], v.ff));
            }
        }
    } /** this variant can cause duplicate items in the priority queue**/
}