#include "bits/stdc++.h"
#include "crocodile.h"
#define i64 long long
using namespace std;
const i64 sz = 1e5 + 5;
vector<vector<i64>> aj[sz];
i64 f[sz], s[sz];
void dfs(int v, int p = -1) {
if (1 == (int) aj[v].size()) {
return;
}
f[v] = s[v] = INT_MAX;
for (auto& u : aj[v]) {
int to = u[0];
int we = u[1];
if (to != p) {
dfs(to, v);
if (we + s[to] <= f[v]) {
s[v] = f[v];
f[v] = we + s[to];
} else {
s[v] = min(s[v], we + s[to]);
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for (int i = 0; i < M; i ++) {
int a = R[i][0];
int b = R[i][1];
aj[a].push_back({b, L[i]});
aj[b].push_back({a, L[i]});
}
dfs(0);
return s[0];
}
