#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5;
vector<pair<int,int>> adj[maxn];
int dp[maxn],dp2[maxn],x;
bool vis[maxn];
void dfs(int v,int p){
vis[v]=1;
dp[v]=0;
for(auto[u,w]:adj[v])if(u!=p){
dfs(u,v);
dp[v]=max(dp[v],dp[u]+w);
}
}
void dfs2(int v,int p){
if(max(dp[v],dp2[v])<max(dp[x],dp2[x]))x=v;
multiset<int> s;
s.insert(dp2[v]);
for(auto[u,w]:adj[v])if(u!=p)s.insert(w+dp[u]);
for(auto[u,w]:adj[v])if(u!=p){
s.erase(s.find(w+dp[u]));
dp2[u]=w+*s.rbegin();
s.insert(w+dp[u]);
dfs2(u,v);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i=0;i<m;i++){
adj[a[i]].push_back({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
vector<int> v;
for(int i=0;i<n;i++){
if(!vis[i]){
dfs(i,i);
x=i;
dp2[i]=0;
dfs2(i,i);
v.push_back(max(dp[x],dp2[x]));
}
}
sort(v.rbegin(),v.rend());
if(v.size()==1){
return v[0];
}else if(v.size()==2){
return v[0]+v[1]+l;
}else{
return max(v[0],v[2]+l)+v[1]+l;
}
}
