void Floyd(vector<vector<pair<int, int>>>& G, int s)
{

    vector<vector<double>> D;
    D.assign(G.size(), vector<double>());
    for (int i = 0; i < G.size(); i++)
    {
        D[i].assign(G.size(), INFINITY);
        D[i][i] = 0;
        for (auto j : G[i])
        {
            D[i][j.first] = j.second;
        }
    }

    for (int k = 0; k < G.size(); k++)
    {
        for (int i = 0; i < G.size(); i++)
        {
            for (int j = 0; j < G.size(); j++)
            {
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }

    for (int i = 0; i < D.size(); i++)
    {
        cout << i+1<<": ";
        for (int j = 0; j < D[i].size(); j++)
        {
            cout << D[i][j];
            if (j != D[i].size() - 1)
                cout << ", ";
        }
        cout << endl;
    }
}