#include "dreaming.h"
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=1e5+5;
const long long INF=1e18;
vector<pair<int, int>> E[N];
bool vis[N];
long long res=0;
long long dol[N], dolid[N], dol2[N];
void dfs(int v){
vis[v]=1;
dolid[v]=-1;
dol[v]=dol2[v]=0;
for(auto u:E[v]){
if(!vis[u.st]){
dfs(u.st);
if(dol[u.st]+u.nd>dol[v]){
dol2[v]=dol[v];
dol[v]=dol[u.st]+u.nd;
dolid[v]=u.st;
}
else if(dol[u.st]+u.nd>dol2[v])dol2[v]=dol[u.st]+u.nd;
}
}
//cout<<v<<" "<<dol[v]<<" "<<dolid[v]<<" "<<dol2[v]<<"\n";
}
long long dfs2(int v, long long maks){
long long ans=INF;
vis[v]=1;
for(auto u:E[v]){
if(!vis[u.st]){
if(u.st==dolid[v])ans=min(ans, dfs2(u.st, u.nd+max(maks, dol2[v])));
else ans=min(ans, dfs2(u.st, u.nd+max(maks, dol[v])));
}
}
ans=min(ans, max(maks, dol[v]));
res=max(res, maks+dol[v]);
return ans;
}
int travelTime(int n, int M, int L, int A[], int B[], int T[]) {
for(int i=0; i<M; i++){
E[A[i]].push_back({B[i], T[i]});
E[B[i]].push_back({A[i], T[i]});
}
for(int i=0; i<n;i ++){
if(!vis[i])dfs(i);
}
for(int i=0; i<n; i++)vis[i]=0;
vector<long long > V;
for(int i=0; i<n; i++){
if(!vis[i])V.push_back(dfs2(i, 0));
}
sort(V.begin(), V.end());
reverse(V.begin(), V.end());
//cout<<V.size()<<"\n";
//for(auto i:V)cout<<i<<" ";
// cout<<"\n";
if(V.size()>=2)res=max(res, V[0]+V[1]+L);
if(V.size()>2)res=max(res, V[1]+V[2]+L+L);
return res;
}
