#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 1e5 + 10;
#define ll long long
vector<pair<int, ll>> adj[NN];
ll dp[1001][1001][2];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
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] });
}
for (int i = 0; i < N; i++) {
for (int j = 1; j <= N; j++) {
dp[i][j][0] = dp[i][j][1] = INT64_MAX;
}
}
for (int j = 1; j <= N; j++) {
for (int i = 0; i < K; i++) {
dp[P[i]][j][0] = dp[P[i]][j][1] = 0;
}
for (int i = 0; i < N; i++) {
for (auto [u, w] : adj[i]) {
if (dp[u][j-1][1] + w <= dp[i][j][0]) {
dp[i][j][1] = dp[i][j][0];
dp[i][j][0] = dp[u][j-1][1] + w;
}else if(dp[u][j-1][1] + w <= dp[i][j][1]){
dp[i][j][1] = dp[u][j-1][1] + w;
}
}
}
}
return dp[0][N][1];
}
