#include "dreaming.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
cerr << to_string(h);
if(sizeof ...(t)) cerr << ", ";
DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif
const int INF = 1e9 + 7, N = 1e5 + 7;
V<pi> G[N];
bool vis[N];
int down[N];
void dfs1(int u, int& mx, int p = -1) {
vis[u] = true;
vi aux({0});
for(auto[v, w]:G[u]) if(v != p) {
dfs1(v, mx, u);
down[u] = max(down[u], down[v] + w);
aux.PB(down[v] + w);
}
sort(ALL(aux), greater<>());
if(SZ(aux) > 1) mx = max(mx, aux[0] + aux[1]);
}
void dfs2(int u, int up, int& mn, int p = -1) {
mn = min(mn, max(up, down[u]));
vi aux({up});
for(auto[v, w]:G[u]) if(v != p)
aux.PB(down[v] + w);
sort(ALL(aux), greater<>());
for(auto[v, w]:G[u]) if(v != p) {
int new_up = aux[aux[0] == down[v] + w] + w;
dfs2(v, new_up, mn, u);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
assert(m <= n - 1);
for(int i = 0; i < m; i++) {
G[a[i]].EB(b[i], t[i]);
G[b[i]].EB(a[i], t[i]);
}
int ans = 0;
vi aux;
for(int i = 0; i < n; i++) if(!vis[i]) {
int mx = 0;
dfs1(i, mx);
ans = max(ans, mx);
int mn = INF;
dfs2(i, 0, mn);
aux.PB(mn);
}
sort(ALL(aux), greater<>());
if(SZ(aux) > 1) ans = max(ans, aux[0] + aux[1] + l);
if(SZ(aux) > 2) ans = max(ans, aux[1] + aux[2] + l * 2);
return ans;
}
