#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define N 200005
#define ff first
#define sz(s) (int)s.size()
#define ss second
#define ll long long
vector <pair<ll,ll>> v[N], p[N];
vector <ll> v1;
map <ll,bool> vis, vi;
ll mn, f[N];
ll dfs(ll x){
vis[x] = 1;
for(auto i : v[x]){
if(vis[i.ff] == 0){
p[x].push_back({dfs(i.ff) + i.ss, i.ff});
}
}
p[x].push_back({0,-1});
sort(p[x].begin(), p[x].end());
return p[x].back().ff;
}
void df(ll x){
vi[x] = 1;
mn = min(mn,max(p[x].back().ff,f[x]));
for(auto i : v[x]){
if(vi[i.ff] == 0){
ll y = p[x].back().ff;
if(p[x].back().ss == i.ff) y = p[x][sz(p[x]) - 2].ff;
f[i.ff] = (max(y,f[x]) + i.ss);
}
}
for(auto i : v[x]){
if(vi[i.ff] == 0) df(i.ff);
}
return;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vis.clear();
v1.clear();
vi.clear();
for(int i = 0; i < n; i++){
v[i].clear();
p[i].clear();
f[i] = 0;
}
for(int i = 0; i < m; i++){
v[a[i]].push_back({b[i],t[i]});
v[b[i]].push_back({a[i],t[i]});
}
for(int i = 0; i < n; i++){
if(vis[i] == 0){
dfs(i);
mn = INT_MAX;
df(i);
v1.push_back(mn);
}
}
sort(v1.begin(), v1.end());
ll k = v1.back();
if(sz(v1) >= 2) k = max(k,v1.back() + l + v1[sz(v1) - 2]);
if(sz(v1) >= 3) k = max(k, v1[sz(v1) - 3] + l*2 + v1[sz(v1) - 2]);
return k;
}
