#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 10;
const ll INF = 1e18;
int marc_1[MAXN], marc_2[MAXN];
vector<pair<int, int>> adj[MAXN];
pair<ll, ll> dp_1[MAXN];
ll dp_2[MAXN];
void dfs_1(int v){
marc_1[v] = 1;
dp_1[v] = {0, 0};
for(auto [u, w] : adj[v]){
if(!marc_1[u]){
dfs_1(u);
if(dp_1[u].first + w >= dp_1[v].first){
dp_1[v] = {dp_1[u].first + w, dp_1[v].first};
} else dp_1[v].second = max(dp_1[v].second, dp_1[u].first + w);
}
}
}
vector<int> comp;
void dfs_2(int v){
comp.push_back(v);
marc_2[v] = 1;
for(auto [u, w] : adj[v]){
if(!marc_2[u]){
ll x = dp_1[v].first;
if(x - w == dp_1[u].first) x = dp_1[v].second;
dp_2[u] = max(dp_2[v], x) + w;
dfs_2(u);
}
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]){
for(int i=1; i<=n; i++){
adj[i].clear();
marc_1[i] = marc_2[i] = 0;
}
for(int i=0; i<m; i++){
adj[a[i] + 1].push_back({b[i] + 1, t[i]});
adj[b[i] + 1].push_back({a[i] + 1, t[i]});
}
vector<ll> prof;
ll ans = 0;
for(int i=1; i<=n; i++){
if(!marc_1[i]){
dfs_1(i);
comp.clear();
dfs_2(i);
ll min_dp = INF;
for(auto v : comp){
ans = max(ans, dp_1[v].first + dp_1[v].second);
min_dp = min(min_dp, max(dp_1[v].first, dp_2[v]));
}
prof.push_back(min_dp);
}
}
sort(prof.rbegin(), prof.rend());
if(prof.size() >= 2) ans = max(ans, prof[0] + prof[1] + l);
if(prof.size() >= 3) ans = max(ans, prof[1] + prof[2] + 2 * l);
return ans;
}
