struct edge {
    ll to, cost;
    bool operator< (const edge& other) const {
        return cost > other.cost;
    }
};

ll dist[N];
vector<edge> G[N];

void dijkstra(int src) {
    memset(dist, 0x7F, sizeof(dist));
    dist[src] = 0;
    priority_queue<edge> minn;
    minn.push({src, 0});
    while (!minn.empty()) {
        auto r = minn.top();
        minn.pop();
        ll u = r.to, cost = r.cost;

        if (dist[u] < cost) continue;

        for (edge& e : G[u]) {
            ll to = e.to, c = e.cost;
            if (dist[to] > dist[u] + c) {
                dist[to] = dist[u] + c;
                minn.push({to, dist[to]});
            }
        }
    }
}

void clear() {
    for (int i = 0; i < n; ++i) G[i].clear();
}