#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int inf = 2e9;
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vector<vector<array<int,2>>> g(n);
for(int i = 0; i < m; i ++ ) {
g[a[i]].push_back({b[i], t[i]});
g[b[i]].push_back({a[i], t[i]});
};
vector<int> ds, us(n), sub(n,0);
function<void(int,int)> st = [&](int ps, int pr) {
us[ps] = 1;
for(auto [to, w] : g[ps]) {
if(to == pr)continue;
st(to, ps);
sub[ps] = max(sub[ps], sub[to] + w);
};
};
int mn = inf;
function<void(int, int, int)> dfs = [&](int ps, int dad, int dw){
vector<int> pr(g[ps].size()+1), sf(g[ps].size()+1);
for(int i = 1; i <= (int)g[ps].size(); i ++ ) {
auto &[to, w] = g[ps][i-1];
pr[i] = pr[i-1];
if(to == dad)continue;
pr[i] = max(pr[i], sub[to]+w);
};
for(int i = g[ps].size()-1; i >= 0; i -- ) {
auto &[to, w] = g[ps][i];
sf[i] = sf[i+1];
if(to == dad)continue;
sf[i] = max(sf[i], sub[to]+w);
};
for(int i = 0; i < (int)g[ps].size(); i ++ ) {
auto &[to, w] = g[ps][i];
if(to == dad)continue;
dfs(to, ps, max({w + dw, sf[i+1]+w, pr[i]+w}));
};
mn = min(mn, max(sub[ps], dw));
//cout << ps << ' ' << dad << ' ' << dw << ' ' << pr.back() << '\n';
};
for(int i = 0; i < n; i ++ ) {
if(us[i])continue;
st(i, i);
mn = inf;
dfs(i, i, 0);
ds.push_back(mn);
};
int ans = 0;
sort(ds.rbegin(), ds.rend());
if(ds.size() > 1) {
ans = max(ds[0]+ds[1]+l, ans);
};
if(ds.size() > 2) {
ans = max(ds[1] + ds[2] + l + l, ans);
};
//for(int i : ds) cout << i << ' ';
//cout << '\n';
//vector<int> ls, ch(n);
//function<void(int,int, vector<int>&)> dfs2 = [&](int ps, int pr, vector<int> &d) {
//ls.push_back(ps);
//ch[ps] = 1;
//for(auto [to, w] : g[ps]) {
//if(to == pr)continue;
//d[to] = d[ps] + w;
//dfs2(to, ps, d);
//};
//};
//vector<int> d(n, 0);
//for(int i = 0; i < n; i ++ ) {
//if(ch[i])continue;
//dfs2(i,i,d);
//int nt = ls[0];
//for(int x : ls)
//if(d[nt] < d[x])nt = x;
//d[nt] = 0;
//dfs2(nt,nt,d);
//for(int x : ls) ans = max(ans, d[x]);
//}
return ans;
}
