// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "dreaming.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
vector<pii> v[maxn];
int pr[maxn], prv[maxn], h[maxn];
bool mark[maxn];
int far(int u, int par = -1){
mark[u] = 1;
if(par == -1)
h[u] = 0;
int ans = u;
for(pii p : v[u]){
int y = p.F, c = p.S;
if(y != par){
h[y] = h[u] + c;
pr[y] = u;
prv[y] = c;
int x = far(y, u);
if(h[x] > h[ans])
ans = x;
}
}
return ans;
}
int TIME = 0;
int travelTime(int n, int m, int L, int a[], int b[], int t[]){
assert(++TIME <= 1);
for(int i = 0; i < m; i++){
v[a[i]].PB({b[i], t[i]});
v[b[i]].PB({a[i], t[i]});
}
int ans = 0;
vector<int> vec;
for(int i = 0; i < n; i++){
if(!mark[i]){
int A = far(i), B = far(A);
int tmp = B, tmpv = 0, LST = -1;
ans = max(ans, h[B]);
while(tmpv + tmpv < h[B]){
LST = prv[tmp];
tmpv+= prv[tmp];
tmp = pr[tmp];
}
tmpv = min(tmpv, h[B] - tmpv + LST);
vec.PB(tmpv);
}
}
if(sz(vec) == 1)
return ans;
if(sz(vec) == 2)
return max(ans, vec[0] + vec[1] + L);
sort(vec.begin(), vec.end());
int A = vec[sz(vec)-3], B = vec[sz(vec)-2], C = vec[sz(vec)-1];
return max({ans, L + B + C, L + L + A + B});
}
