vector<int> dijkstra(int v, vector<vector<int>> adj[], int src){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,src});
    vector<int> dist(v,1e9);
    while(!pq.empty()){
        int node = pq.front().second;
        int dis = pq.front().first;
        pq.pop();
        for(auto it:adj[node]){
            int edgWeight = it[1];
            int adjNode = it[0];
            if(edgWeight + dis < dist[adjNode]){
                dist[adjNode] = edgWeight + dis;
                pq.push({dist[it], it});
            }
        }
    }
    return dist;
}