#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define _ << " " <<
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ull unsigned long long
#define lll __int128
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
const ll mod = 1e9 + 7;
const ll mod1 = 998244353;
const ll naim = 1e9;
const ll max_bit = 60;
const ull tom = ULLONG_MAX;
const ll MAXN = 100005;
const ll LOG = 20;
const ll NAIM = 1e18;
const ll N = 2e6 + 5;
vector<vector<pair<int, int>>> g(MAXN);
bool vis[MAXN];
int par[MAXN];
int weight[MAXN];
int far;
int mx;
void dfs(int u, int p, int d) {
vis[u] = 1;
if(d > mx) {
mx = d;
far = u;
}
for(auto &[v, w] : g[u]) {
if(v == p) continue;
par[v] = u;
weight[v] = w;
dfs(v, u, w + d);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i = 0; i < m; i++) {
g[a[i]].pb({b[i], t[i]});
g[b[i]].pb({a[i], t[i]});
}
int mx_diagram = 0;
vector<int> r;
for(int i = 0; i < n; i++) {
if(!vis[i]) {
mx = -1;
dfs(i, -1, 0);
int node1 = far;
mx = -1;
dfs(node1, -1, 0);
int node2 = far;
mx_diagram = max(mx_diagram, mx);
int cur = node2;
int mn = mx;
int d = 0;
while(cur != node1) {
mn = min(mn, max(d, mx - d));
d += weight[cur];
cur = par[cur];
}
mn = min(mn, max(d, mx - d));
r.pb(mn);
}
}
sort(rall(r));
int ans = mx_diagram;
if(r.size() >= 2) ans = max(ans, r[0] + r[1] + l);
if(r.size() >= 3) ans = max(ans, r[1] + r[2] + l * 2);
return ans;
}
