#include "crocodile.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define speedup cin.tie(0)->sync_with_stdio(0);
#define bitcount __builtin_popcount
#define all(x) begin(x), end(x)
#define pb push_back
#define vc vector
using ll = long long;
using pii = array<int, 2>;
mt19937 mt(chrono::steady_clock().now().time_since_epoch().count());
template<class T> inline bool chmin(T &a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}
const ll inf = 4*1e9, N = 1e3 + 1;
static int dp[N][N];
static int memo[N][N];
int travel_plan(int n, int m, int ed[][2], int l[], int k, int p[]) {
vc<vc<int>> adj (n + 1);
for (int i = 0; i < m; i++) {
ed[i][0]++;
ed[i][1]++;
adj[ed[i][0]].pb(i);
adj[ed[i][1]].pb(i);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = inf;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < k; j++) {
dp[p[j] + 1][i] = 0;
memo[p[j] + 1][i] = 1;
}
}
auto dfs = [&](auto &&dfs, int u, int p) -> ll {
if (memo[u][p]) return dp[u][p];
dp[u][p] = inf;
int mn0 = inf, mn1 = inf;
for (int i : adj[u]) {
int v = ed[i][0], w = l[i];
if (v == u) v = ed[i][1];
if (v == p) continue;
int cost = dfs(dfs, v, u);
if (cost < inf) {
cost += 1ll * w;
if (mn0 > cost) mn1 = mn0, mn0 = cost;
else chmin(mn1, cost);
}
}
memo[u][p] = 1;
return dp[u][p] = mn1;
};
int res = dfs(dfs, 1, 1);
if (res >= inf) return -1;
return res;
}
/*
5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7
*/
