#include "crocodile.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
vector <vector <pair <int, int>>> adj;
vector <int> vis;
vector <long long> fin;
void init(int u, int w) {
if (adj[u].size() == 1) {
fin[u] = w;
}
vis[u] = 1;
for (auto x : adj[u]) {
if (vis[x.ff]) continue;
init(x.ff, w + x.ss);
}
}
void dfs(int u) {
int m = INT_MAX, m1 = INT_MAX;
vis[u] = 1;
for (auto [x, y] : adj[u]) {
if (vis[x]) continue;
dfs(x);
if (fin[x] < m) {
m1 = m;
m = fin[x];
}
else if (fin[x] < m1) {
m1 = fin[x];
}
}
if (adj[u].size() >= 3) {
fin[u] = m1;
}
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
adj.resize(n);
vis.resize(n, 0);
fin.resize(n, 0);
for (int i = 0;i < m;i++) {
adj[r[i][0]].push_back({r[i][1], l[i]});
adj[r[i][1]].push_back({r[i][0], l[i]});
}
init(0, 0);
vis.clear();
vis.resize(n, 0);
dfs(0);
return fin[0];
}
//int main() {
//}
