void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (arr[i][j].second >arr[i][k].second + arr[k][j].second) {
                    arr[i][j].second = arr[i][k].second + arr[k][j].second;
                    arr[i][j].first= arr[i][k].first + arr[k][j].first;
                }
                else if (arr[i][j].second == arr[i][k].second + arr[k][j].second)

                    arr[i][j].first =min(arr[i][j].first, arr[i][k].first + arr[k][j].first);
    }
}