#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int NMAX = 1e5;
const ll INF = 1e18;
vector<pair<int, int>> g[NMAX + 1];
ll dp[NMAX + 1];
void DFS(int node, int dad = 0) {
if(g[node].size() == 1) {
return;
}
// dp[node] = INF;
ll dp1 = INF, dp2 = INF;
for(auto [next_node, edge_value] : g[node]) {
if(next_node != dad) {
DFS(next_node, node);
if(dp[next_node] + edge_value < dp1) {
dp2 = dp1;
dp1 = dp[next_node] + edge_value;
}
else if(dp[next_node] + edge_value == dp1 && dp[next_node] + edge_value < dp2) {
dp2 = dp[next_node] + edge_value;
}
}
}
dp[node] = dp2;
}
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]; a++;
int b = R[i][1]; b++;
int c = L[i];
// cout << a << ' ' << b << ' ' << c << '\n';
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
for(int i = 0; i < K; i++) {
P[i]++;
}
DFS(1);
return dp[1];
}
