#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double; // or double, if TL is tight
using str = string;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
struct fun {
ll ct = 0;
vll V;
fun &operator+=(const fun &rhs) {
ct += rhs.ct;
for(auto it : rhs.V)
V.push_back(it);
return *this;
}
fun clean(ll w) {
sort(all(V));
deque<ll> D;
for(auto it : V) D.push_back(it);
V.clear();
while(D.size() > 2) {
ct += D.back() - D.front();
D.pop_back();
D.pop_front();
}
for(auto it : D) V.push_back(it + w);
if(V.size() == 1) V.push_back(V.back());
return *this;
}
ll eval() {
sort(all(V));
deque<ll> D;
for(auto it : V) D.push_back(it);
V.clear();
while(!D.empty()) {
ct += D.back() - D.front();
D.pop_back();
if(!D.empty())
D.pop_front();
}
return ct;
}
ll ev(ll i) {
ll val = ct;
for(auto it : V) val += abs(it - i);
return val;
}
};
struct tree {
ll n;
ll limExp;
vi par;
vector<vector<ii> > L, G;
tree(ll N, ll LimExpl) : n(N), limExp(LimExpl), par(N), L(N), G(N) {}
void add_edge(ll u, ll v, ll w) {
L[u].push_back({v, w});
L[v].push_back({u, w});
}
void init() {
function<fun(ll, ll)> dfs = [&](ll u, ll p) {
if(u >= limExp) { /// frunza cu bomba, nu face nimic
fun re;
re.V.push_back(0);
re.V.push_back(0);
return re;
}
fun re;
for(auto [it, w] : L[u])
if(it != p) {
auto fiu = dfs(it, u).clean(w);
re += fiu;
}
return re;
};
cout << dfs(0, -1).eval() / 2 << "\n";
}
};
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
ll n, m;
cin >> n >> m;
tree T(n + m, n);
for(ll i = 1; i < n + m; ++i) {
ll u, v, w;
cin >> u >> w;
--u;
T.add_edge(u, i, w);
}
T.init();
return 0;
}
