#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 = 2e9;
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(di[rt], array<int,2>{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]);
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);
ans=max(ans,di[1][0]);
best = -1;
mark(i);
ar.push_back(best);
}
sort(all(ar));
if(sz(ar) == 1) return ans;
if(sz(ar) == 2){
ans=max(ans, ar[0] + ar[1] + L);
return ans;
}
int xd = sz(ar) - 1;
ans=max(ans, ar[xd] + ar[xd - 1] + L);
ans=max(ans, ar[xd-1] + ar[xd-2] + 2 * L);
return ans;
}
/*void _(){
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
