#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> g(100005);
int rv[5],dub[100005];
bitset<100005> vis;
int dalj(int p, int q, int wq)
{
int ret=p; dub[p]=dub[q]+wq;
for (auto [it,w] : g[p]) if (it!=q)
{
int tmp=dalj(it,p,w);
if (dub[tmp]>dub[ret]) ret=tmp;
}
return ret;
}
bool naso;
vector<int> path;
void put(int p, int q, int wq, int s)
{
if (!naso) path.push_back(wq);
if (p==s) naso=true;
for (auto [it,w] : g[p]) if (it!=q) put(it,p,w,s);
if (!naso) path.pop_back();
}
void dfs(int p, int q)
{
vis[p]=1;
for (auto [it,w] : g[p]) if (it!=q) dfs(it,p);
}
vector<int> niz;
int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
dub[-1]=-1;
int wtf=0;
for (int i=0;i<m;i++) g[A[i]].push_back({B[i],T[i]}),g[B[i]].push_back({A[i],T[i]});
for (int i=0;i<n;i++) if (!vis[i])
{
int a=dalj(i,-1,0),b=dalj(a,-1,0);
naso=false,path.clear(),put(a,-1,0,b);
int s=0;
for (auto it : path) s+=it;
int tmp=0;
for (auto it : path)
{
tmp+=it;
if (2*tmp>=s)
{
niz.push_back(min(tmp,s+it-tmp));
break;
}
}
wtf=max(wtf,s);
dfs(i,-1);
}
//for (auto it : niz) cout<<it<<" "; cout<<endl;
sort(niz.begin(),niz.end(),greater<int>());
if (niz.size()==1) return max(wtf,niz[0]);
if (niz.size()==2) return max(wtf,niz[0]+niz[1]+L);
return max(wtf,max(niz[0]+niz[1]+L,niz[1]+niz[2]+2*L));
}
