#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 545 , inf = 1e9 + 199;
#include "dreaming.h"
vector<pair<int , int>> g[N];
vector<int> color(N) , dp(N , 1) , dp2(N , 0) , dp3(N , 0),pre(N,0),pre1(N,0);
int mx = -1 , ind = -1;
void dfs(int s , int p) {
color[s] = 1;
if(dp[s] > mx){
mx=dp[s];
ind=s;
}
for(auto &i : g[s]) {
if( i.first == p){
continue;
}
dp[ i.first ] = dp[s] + i.second;
pre[i.first]=s;
pre1[i.first]=i.second;
dfs( i.first , s);
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
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]});
}
vector<int> atvet;
int cavab=0;
for(int i=0;i<n;i++) {
if(color[i] == 0) {
mx=ind=-1;
dp[i]=0;
dfs(i , i);
int ind1=ind;
mx=ind=-1;
dp[ind1]=0;
dfs(ind1 , ind1);
int e=ind;
int mx1=mx;
int sum=0;
while(e!=ind1){
sum+=pre1[e];
e=pre[e];
mx1=min(mx1,max(mx-sum,sum));
}
atvet.push_back(mx1);
cavab=max(cavab,mx);
}
}
sort(atvet.begin() , atvet.end());
reverse(atvet.begin() , atvet.end());
if(atvet.size()>=2){
cavab=max(cavab,atvet[0]+atvet[1]+l);
}
if(atvet.size()>=3){
cavab=max(cavab,atvet[1]+atvet[2]+2*l);
}
return cavab;
}
