#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef pair<int, int> pii;
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define SZ(x) int(x.size())
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
int mark[MAXN] , dpDown[MAXN] , dpUp[MAXN];
vector<int> vec;
vector<pii> adj[MAXN];
void DFSDown(int v , int p = -1){
mark[v] = 1;
vec.push_back(v);
for(pii i : adj[v]){
int u = i.X , w = i.Y;
if(u == p) continue;
DFSDown(u , v);
dpDown[v] = max(dpDown[v] , dpDown[u] + w);
}
}
void DFSUp(int v , int p = -1){
int mx = 0;
for(pii i : adj[v]){
int u = i.X , w = i.Y;
if(u == p) continue;
dpUp[u] = max(dpUp[v] , mx) + w;
mx = max(mx , dpDown[u] + w);
}
reverse(all(adj[v])); mx = 0;
for(pii i : adj[v]){
int u = i.X , w = i.Y;
if(u == p) continue;
dpUp[u] = max(dpUp[u] , max(dpUp[v] , mx) + w);
mx = max(mx , dpDown[u] + w);
// cout << v << ' ' << u << ' ' << mx << endl;
DFSUp(u , v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0 ; i < M ; i++){
adj[A[i]].push_back({B[i] , T[i]});
adj[B[i]].push_back({A[i] , T[i]});
}
int ans = 0;
vector<int> v;
for(int i = 0 ; i < N ; i++){
if(mark[i]) continue;
vec = {};
DFSDown(i);
DFSUp(i);
int R = MOD * 2;
for(int j : vec){
int cur = max(dpDown[j] , dpUp[j]);
R = min(R , cur);
ans = max(ans , cur);
}
v.push_back(R);
// cout << R << endl;
}
sort(all(v) , greater<int>());
if(SZ(v) >= 2) ans = max(ans , v[0] + v[1] + L);
if(SZ(v) >= 3) ans = max(ans , v[1] + v[2] + L + L);
return ans;
//cout << N << endl;
//for(int i = 0 ; i < N ; i++) cout << i << ' ' << dpDown[i] << ' ' << dpUp[i] << endl;
}
