#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int INF = 987654321;
int N, M, L;
vector<pii> adj[MAXN+10];
bool vis[MAXN+10];
int DA[MAXN+10], DB[MAXN+10], ans;
void dfs(int now, int bef, int *dist, int dep, vector<int> &V)
{
dist[now]=dep; vis[now]=true; V.push_back(now);
for(auto nxt : adj[now])
{
if(nxt.first==bef) continue;
dfs(nxt.first, now, dist, dep+nxt.second, V);
}
}
int travelTime(int _N, int _M, int _L, int _A[], int _B[], int _T[])
{
int i, j;
N=_N; M=_M; L=_L;
for(i=0; i<M; i++)
{
int u=_A[i]+1, v=_B[i]+1, w=_T[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> S;
for(i=1; i<=N; i++)
{
if(vis[i]) continue;
int u, v; vector<int> V;
V.clear(); dfs(i, i, DA, 0, V);
u=i; for(auto it : V) if(DA[u]<DA[it]) u=it;
V.clear(); dfs(u, u, DA, 0, V);
v=u; for(auto it : V) if(DA[v]<DA[it]) v=it;
V.clear(); dfs(v, v, DB, 0, V);
ans=max(ans, DB[u]);
int now=INF;
for(auto it : V) now=min(now, max(DA[it], DB[it]));
S.push_back(now);
}
sort(S.begin(), S.end(), greater<int>());
if(S.size()>=2) ans=max(ans, S[0]+S[1]+L);
if(S.size()>=3) ans=max(ans, S[1]+S[2]+L+L);
return ans;
}
