#include <bits/stdc++.h>
#include "dreaming.h"
#define ve vector
#define all(x) x.begin(), x.end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5+10;
ve<pii> g[MAXN];
bool vis[MAXN];
int dp[MAXN];
void calcdst(int v){
vis[v] = 1;
dp[v] = 0;
for(auto to : g[v])
if(!vis[to.fi]){
calcdst(to.fi);
dp[v] = max(dp[v], dp[to.fi] + to.se);
}
}
int dfs(int v, int p, int curmx){
ve<int> dsts = {curmx};
for(auto& to : g[v])
if(to.fi != p)
dsts.push_back(dp[to.fi] + to.se);
sort(all(dsts), greater<int>());
int res = dsts[0];
multiset<int, greater<int> > cdst;
for(auto i : dsts)
cdst.insert(i);
for(auto& to : g[v])
if(to.fi != p){
cdst.erase(cdst.find(dp[to.fi] + to.se));
res = min(res, dfs(to.fi, v, *cdst.begin() + to.se));
cdst.insert(dp[to.fi] + to.se);
}
return res;
}
int dfs2(int v, int p, int curmx){
ve<int> dsts = {curmx};
for(auto to : g[v])
if(to.fi != p)
dsts.push_back(dp[to.fi] + to.se);
sort(all(dsts), greater<int>());
int res = dsts[0];
if(dsts.size() != 1)
res += dsts[1];
multiset<int, greater<int> > cdst;
for(auto i : dsts)
cdst.insert(i);
for(auto& to : g[v])
if(to.fi != p){
cdst.erase(cdst.find(dp[to.fi] + to.se));
res = max(res, dfs2(to.fi, v, *cdst.begin() + to.se));
cdst.insert(dp[to.fi] + to.se);
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int sum = 0;
for(int i = 0; i < M; i++){
int u = A[i], v = B[i], w = T[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
sum += w;
}
ve<int> v;
int res = 0;
for(int i = 0; i < N; i++)
if(!vis[i]){
calcdst(i);
v.push_back(dfs(i, i, 0));
res = max(res, dfs2(i, i, 0));
}
sort(all(v), greater<int>());
if(v.size() == 1)
res = max(res, v[0]);
else if(v.size() == 2)
res = max(res, v[0] + v[1] + L);
else
res = max({res, v[0] + v[1] + L, v[1] + v[2] + 2*L});
return res;
}
