#include "bits/stdc++.h"
#include "dreaming.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 1e5 + 5;
const int INF = 1e9;
vector<array<int,2>> v[N];
int vis[N],dist[N], ans = 0, best = -1;
array<int,2> di[2];
void dfs(int c,int p,int d,int rt){
di[rt] = max({d, c});
for(auto [u, w] : v[c]){
if(u == p) continue;
dfs(u,c,w+d,rt);
}
}
void calc(int c,int p,int d){
dist[c] = max(dist[c], d);
for(auto [u,w] : v[c]){
if(u == p) continue;
calc(u,c,d + w);
}
}
void mark(int c){
if(vis[c]) return;
if(best == -1) best = dist[c];
else best = min(best, dist[c]);
ans = max(ans, dist[c]);
vis[c] = 1;
for(auto [u,w] : v[c]) mark(u);
}
int travelTime(int _n, int _m, int L, int A[], int B[], int T[]) {
int n = _n, m = _m;
for(int i=0;i<m;i++){
int a = A[i],b = B[i],c = T[i];
v[a].push_back({b,c});
v[b].push_back({a,c});
}
vector<int> ar;
for(int i=0;i<n;i++){
if(vis[i]) continue;
di[0] = di[1] = {0, 0};
dfs(i,i,0,0);
dfs(di[0][1],di[0][1],0,1);
calc(di[0][1],di[0][1],0);
calc(di[1][1],di[1][1],0);
best = -1;
mark(i);
ar.push_back(best);
}
sort(all(ar));
int l = 0, r = sz(ar) - 1, ok = 0;
vector<int> val(sz(ar));
for(int i=0;i<sz(ar);i++){
if(ok) val[l++] = ar[i];
else val[r--] = ar[i];
ok ^= 1;
}
int lf = -INF;
for(int i=0;i<sz(val);i++){
int cur = val[i] + L * i;
if(i) ans=max(ans,cur+lf);
lf = max(lf, val[i] - L * i);
}
return ans;
}
/*void _(){
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
