В этой задаче нужно реализовать алгоритм Дейкстры за O(mlogn). Про алгоритм можно почитать здесь https://ru.algorithmica.org/cs/shortest-paths/dijkstra/

Я подписала в задаче, к сожалению в реализации используется сет на дереве, в ванильном питоне он не реализован, пример реализации на c++:
vector<int> dijkstra(int s) {
    vector<int> d(n, inf);
    d[root] = 0;
    set< pair<int, int> > q;
    q.insert({0, s});
    while (!q.empty()) {
        int v = q.begin()->second;
        q.erase(q.begin());
        for (auto [u, w] : g[v]) {
            if (d[u] > d[v] + w) {
                q.erase({d[u], u});
                d[u] = d[v] + w;
                q.insert({d[u], u});
            }
        }
    }
    return d;
}