#include "dreaming.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5 + 10;
int mk[N], fr[N], to[N], w[N];
vector<int> G[N], vis;
int dp[N], dp2[N];
void DFS(int u){
mk[u] = 1;
vis.pb(u);
int adj;
for(auto e : G[u]){
adj = to[e] ^ fr[e] ^ u;
if(!mk[adj]){
DFS(adj);
dp[u] = max(dp[u], dp[adj] + w[e]);
}
}
}
void DFS2(int u, int p){
int adj, res = dp2[u];
for(auto e : G[u]){
adj = to[e] ^ fr[e] ^ u;
if(adj == p) continue;
dp2[adj] = max(res + w[e], dp2[adj]);
res = max(res, dp[adj] + w[e]);
}
reverse(G[u].begin(), G[u].end());
res = dp2[u];
for(auto e : G[u]){
adj = to[e] ^ fr[e] ^ u;
if(adj == p) continue;
dp2[adj] = max(res + w[e], dp2[adj]);
res = max(res, dp[adj] + w[e]);
DFS2(adj, u);
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for(int i = 0; i < m; i++){
fr[i] = A[i];
to[i] = B[i];
G[A[i]].pb(i);
G[B[i]].pb(i);
w[i] = T[i];
}
vector<int> V;
for(int i = 0; i < n; i++){
if(mk[i]) continue;
vis.clear();
DFS(i);
DFS2(i, -1);
int res = 2000000000;
for(auto x : vis) res = min(res, max(dp[x], dp2[x]));
V.pb(res);
}
sort(V.begin(), V.end());
reverse(V.begin(), V.end());
int ans = V[0];
if(V.size() >= 2) ans = max(ans, L + V[0] + V[1]);
if(V.size() >= 3) ans = max(ans, L + L + V[1] + V[2]);
return ans;
}
