#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int NMAX = 1e5;
const ll INF = 1e18;
struct PQElement {
int node, parent, edge_parent;
ll d;
bool operator < (const PQElement &other) const {
return other.d < d;
}
};
vector<pair<int, int>> g[NMAX + 1];
vector<pair<int, int>> g1[NMAX + 1];
int n, m;
vector<ll> d[NMAX + 1];
vector<pair<int, int>> parents[NMAX + 1];
char is_end[NMAX + 1];
ll dp[NMAX + 1][2];
int indegree[NMAX + 1];
void Dijkstra(int start) {
priority_queue<PQElement> pq;
pq.push({start, 0, 0, 0});
while(!pq.empty()) {
auto [node, parent, edge_parent, curent_d] = pq.top();
pq.pop();
if(d[node].size() < 1) {
d[node].push_back(curent_d);
parents[node].emplace_back(parent, edge_parent);
if(!is_end[node]) {
for(auto [next_node, edge_d] : g[node]) {
pq.push({next_node, node, edge_d, curent_d + edge_d});
}
}
}
}
}
void CreateDAG() {
for(int i = 2; i <= n; i++) {
for(auto [j, c] : parents[i]) {
g1[i].emplace_back(j, c);
}
}
for(int i = 1; i <= n; i++) {
sort(g1[i].begin(), g1[i].end());
g1[i].erase(unique(g1[i].begin(), g1[i].end()), g1[i].end());
for(auto [j, c] : g1[i]) {
indegree[j]++;
}
}
}
void Update(ll dp[], ll dp_value) {
if(dp_value < dp[0]) {
dp[1] = dp[0];
dp[0] = dp_value;
}
else if(dp_value < dp[1]) {
dp[1] = dp_value;
}
}
void SolveDP() {
for(int i = 1; i <= n; i++) {
dp[i][0] = dp[i][1] = INF;
}
queue<int> q;
for(int i = 1; i <= n; i++) {
if(!indegree[i]) {
q.push(i);
if(is_end[i]) {
dp[i][0] = dp[i][1] = 0;
}
}
}
while(!q.empty()) {
int node = q.front();
q.pop();
for(auto [next_node, edge_d] : g1[node]) {
Update(dp[next_node], dp[node][1] + edge_d);
indegree[next_node]--;
if(!indegree[next_node]) {
q.push(next_node);
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N; m = M;
for(int i = 0; i < M; i++) {
int a = R[i][0]; a++;
int b = R[i][1]; b++;
int c = L[i];
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
for(int i = 0; i < K; i++) {
P[i]++;
is_end[P[i]] = 1;
}
Dijkstra(1);
// for(int i = 1; i <= n; i++) {
// for(auto [j, c] : parents[i]) {
// cout << i << ' ' << j << ' ' << c << '\n';
// }
// }
CreateDAG();
SolveDP();
// for(int i = 1; i <= n; i++) {
// for(auto [j, c] : g1[i]) {
// cout << i - 1 << ' ' << j - 1 << ' ' << c << '\n';
// }
// }
return dp[1][1];
}
