#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;
int travel_plan(int n, int m, int (*r)[2], int *l, int k, int *p){
const ll inf = 1e18;
vector<vector<bool>> edg(n, vector<bool>(n));
vector<pair<int,ll>> adj[n];
vector<bool> end(n);
vector<ll> val(n,0);
li(i,0,m){
edg[r[i][0]][r[i][1]] = 1;
edg[r[i][1]][r[i][0]] = 1;
adj[r[i][0]].pb({r[i][1],l[i]});
adj[r[i][1]].pb({r[i][0],l[i]});
}
li(i,0,n){
if(end[i]) continue;
ll b=inf,sb=inf;
for(auto u : adj[i]){
if(!end[u.F]) continue;
ll v = val[u.F] + u.S;
if(v<b){
sb=b;
b=v;
}
else if (v < sb && v != b){
sb=v;
}
}
if(sb!=inf){
val[i]=sb;
end[i]=1;
}
}
return val[0];
}
