vector<pair<long, int>> shortestReach(int n, const vector<vector<pair<int, int>>>& edges, int s) {
    vector<bool> visited(n+1);
    vector<pair<long, int>> distance(n+1, {LONG_MAX, -1});
    distance[s] = {0, s};
    for (int count = 1; count <= n; ++count) {
        int shortest = -1;
        for (int i = 1; i <= n; ++i) {
            if (!visited[i] and (shortest == -1 or distance[shortest].first > distance[i].first)) shortest = i;
        }
        visited[shortest] = true;
        if (shortest == -1 or distance[shortest].first == LONG_MAX) break;
        for (auto neighbor : edges[shortest]) {
            int u = neighbor.first, W = neighbor.second;
            if (!visited[u]) distance[u].first = min(distance[u].first, distance[shortest].first + W);
        }
    }    
    return distance;
}