#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)1e5 + 4;
int N, M;
vector<pair<int, int>> way[NS];
int chk[NS];
int ans, dir[NS];
vector<int> lens, sufs, hs;
pair<int, int> dfs(int x, int from){
chk[x] = 1;
pair<int, int> rv = {0, x};
for(auto&nxt:way[x]){
if(nxt.first == from){
continue;
}
dir[nxt.first] = x;
auto nval = dfs(nxt.first, x);
nval.first += nxt.second;
rv = max(rv, nval);
}
return rv;
}
void push(int now, int to){
if(now == to){
return;
}
for(auto&nxt:way[now]){
if(nxt.first != dir[now]){
continue;
}
lens.push_back(nxt.second);
push(nxt.first, to);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; ++i){
way[A[i]].push_back({B[i], T[i]});
way[B[i]].push_back({A[i], T[i]});
}
for(int i = 0; i < N; ++i){
if(chk[i]){
continue;
}
auto rv = dfs(i, -1);
int pa = rv.second;
rv = dfs(pa, -1);
int pb = rv.second;
ans = max(ans, rv.first);
lens.clear();
push(pb, pa);
sufs.clear();
int sum = 0;
for(int j = (int)lens.size() - 1; j >= 0; --j){
sum += lens[j];
sufs.push_back(sum);
}
reverse(sufs.begin(), sufs.end());
int half = MOD;
sum = 0;
for(int j = 0; j < (int)lens.size(); ++j){
half = min(half, max(sum, sufs[j]));
sum += lens[j];
}
if((int)lens.size() == 0){
half = 0;
}
hs.push_back(half);
}
sort(hs.begin(), hs.end()), reverse(hs.begin(), hs.end());
if((int)hs.size() >= 2){
ans = max(ans, hs[0] + hs[1] + L);
}
if((int)hs.size() >= 3){
ans = max(ans, hs[1] + hs[2] + L * 2);
}
return ans;
}
