#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 7;
vector<pair<int, int>> adj[N];
int down[N], up[N], dp[N];
bool vst[N];
void Dfs1(int u, int p){
vst[u] = 1;
down[u] = dp[u] = 0;
for(auto e : adj[u]){
int v = e.first;
int c = e.second;
if (v == p)
continue;
Dfs1(v, u);
dp[u] = max(dp[u], down[u] + down[v] + c);
down[u] = max(down[u], down[v] + c);
}
}
void Dfs2(int u, int p, int &best){
best = min(best, max(up[u], down[u]));
multiset<int> s;
s.insert(up[u]);
for(auto e : adj[u]){
int v = e.first;
int c = e.second;
if (v == p)
continue;
s.insert(down[v] + c);
}
for(auto e : adj[u]){
int v = e.first;
int c = e.second;
if (v == p)
continue;
s.erase(s.find(down[v] + c));
up[v] = *(--s.end()) + c;
s.insert(down[v] + c);
Dfs2(v, u, best);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i = 0; i < m; i++){
adj[a[i]].push_back({b[i], t[i]});
adj[b[i]].push_back({a[i], t[i]});
}
int res = 0;
vector<int> vals;
for(int i = 1; i <= n; i++){
if (vst[i])
continue;
int best = 1e9;
Dfs1(i, -1);
Dfs2(i, -1, best);
res = max(res, dp[i]);
vals.push_back(best);
}
sort(vals.begin(), vals.end(), greater<int>());
if (vals.size() >= 2)
res = max(res, vals[0] + vals[1] + l);
if (vals.size() >= 3)
res = max(res, vals[1] + vals[2] + 2 * l);
return res;
}
