void Dijkstra (int s) {
    vector < int > dist(n, INF);
    dist[s] = 0;
    set < pair < int , int > > st;
    st.insert({0, s});
    while (!st.empty()) {
        auto e = *st.begin();
        int v = e.first;
        int d = e.second;
        st.erase(st.begin());
        for (auto u : g[v]) {
            int to = u.first, w = u.second;
            if (dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                dist[to] = dist[v] + w;
                st.insert({dist[to}, to});
            }
        }
    }
}