#include <bits/stdc++.h>
using namespace std;
#define task ""
#define fi first
#define se second
#define MASK(i) (1 << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (b), _a = (a); i >= _a; --i)
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const int INF = 2e9 + 7;
const int MAX = 100100;
int n, m, k;
bool exist[MAX];
vector<pair<int, int>> adj[MAX];
namespace subtask1 {
int dp[MAX];
void dfs(int u, int p) {
if (u && adj[u].size() == 1) {
if (exist[u]) dp[u] = 0;
return;
}
vector<long long> arr;
for (pair<int, int> &x: adj[u]) if (x.fi != p) {
int v = x.fi, w = x.se; dfs(v, u);
if (dp[v] != INF) arr.push_back(w + dp[v]);
}
if (arr.size() > 1) {
sort(all(arr));
dp[u] = arr[1];
}
}
int solve(void) {
for (int i = 0; i < n; ++i) dp[i] = INF; dfs(0, -1);
return (dp[0] == INF ? -1 : dp[0]);
}
}
namespace fullsubtask {
struct node {
int u, t, dist;
node(int _u = 0, int _t = 0, int _dist = 0) {
u = _u; t = _t; dist = _dist;
}
bool operator< (const node &other) const {
return dist > other.dist;
}
};
priority_queue<node> pq;
int d[MAX][2];
int solve(void) {
for (int i = 0; i < n; ++i) d[i][0] = d[i][1] = INF;
for (int i = 0; i < n; ++i) if (exist[i]) {
pq.push(node(i, 1, 0));
d[i][0] = 0;
d[i][1] = 0;
}
while (pq.size()) {
int u = pq.top().u;
int t = pq.top().t;
int dist = pq.top().dist;
pq.pop();
if (t == 0) continue;
if (dist != d[u][t]) continue;
for (pair<int, int> &x: adj[u]) {
int v = x.fi, w = x.se;
for (int i = 0; i < 2; ++i) if (d[v][i] >= dist + w) {
for (int j = 1; j > i; --j) {
if (minimize(d[v][j], d[v][j - 1]) && j)
pq.push(node(v, j, d[v][j]));
}
if (minimize(d[v][i], dist + w) && i)
pq.push(node(v, i, d[v][i]));
break;
}
}
}
return (d[0][1] == INF ? -1 : d[0][1]);
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N; m = M; k = K;
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 < k; ++i) {
exist[P[i]] = true;
}
if (m == n - 1) return subtask1::solve();
return fullsubtask::solve();
}
