#include <bits/stdc++.h>
using namespace std;
vector<map<unsigned, unsigned>> g;
bool find_cycle(unsigned u, vector<unsigned> &c, vector<bool> &vis, unsigned p = -1)
{
if (vis[u])
return 1;
vis[u] = 1;
for (auto const &[v, w] : g[u])
if (v != p)
if (find_cycle(v, c, vis, u))
{
c.push_back(u);
return 1;
}
return 0;
}
// Returns (longest path inside subtree, longest path to root)
pair<uint64_t, uint64_t> longest_tree_path(unsigned u, unsigned p = -1)
{
pair<uint64_t, uint64_t> ans = {0, 0};
for (auto const &[v, w] : g[u])
{
if (v != p)
{
auto const [sl, rl] = longest_tree_path(v, u);
ans.first = max(ans.first, max(sl, ans.second + rl + w));
ans.second = max(ans.second, rl + w);
}
}
return ans;
}
uint64_t longest_simple_path(unsigned u, vector<bool> &cvis)
{
vector<unsigned> c;
find_cycle(u, c, cvis);
if (c.empty())
return longest_tree_path(u).first;
size_t const m = c.size();
vector<uint64_t> root_paths(c.size());
uint64_t ans = 0;
vector<unsigned> pre_dis(c.size()), next_dis(c.size());
for (size_t i = 0; i < m; i++)
{
next_dis[i] = g[c[i]][c[(i + 1) % m]];
pre_dis[i] = g[c[i]][c[(i - 1 + m) % m]];
g[c[i]].erase(c[(i + 1) % m]);
g[c[i]].erase(c[(i - 1 + m) % m]);
auto const [sl, rl] = longest_tree_path(c[i]);
ans = max(ans, sl);
root_paths[i] = rl;
}
int64_t dp = 0, prefix_sum = 0;
for (size_t i = 0; i < m; i++)
{
ans = max(ans, root_paths[i] + prefix_sum + dp);
dp = max(dp, (int64_t)root_paths[i] - (int64_t)prefix_sum);
prefix_sum += next_dis[i];
}
reverse(c.begin(), c.end());
reverse(root_paths.begin(), root_paths.end());
reverse(pre_dis.begin(), pre_dis.end());
dp = 0, prefix_sum = 0;
for (size_t i = 0; i < m; i++)
{
ans = max(ans, root_paths[i] + prefix_sum + dp);
dp = max(dp, (int64_t)root_paths[i] - (int64_t)prefix_sum);
prefix_sum += pre_dis[i];
}
return ans;
}
void mark_component(unsigned u, vector<bool> &vis)
{
vis[u] = 1;
for (auto const &[v, w] : g[u])
if (!vis[v])
mark_component(v, vis);
}
int main()
{
size_t n;
cin >> n;
g = vector<map<unsigned, unsigned>>(n);
for (size_t i = 0; i < n; i++)
{
unsigned u, w;
cin >> u >> w;
g[i][u - 1] = max(g[i][u - 1], w);
g[u - 1][i] = max(g[u - 1][i], w);
}
vector<bool> vis(n, 0), cvis(n, 0);
uint64_t max_distance = 0;
for (unsigned i = 0; i < n; i++)
{
if (!vis[i])
{
mark_component(i, vis);
max_distance += longest_simple_path(i, cvis);
}
}
cout << max_distance << '\n';
}
