#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];
vector <ll> p[N], 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);
}
}
p[x].push_back(0);
sort(p[x].begin(), p[x].end());
return p[x].back();
}
void df(ll x){
vi[x] = 1;
mn = min(mn,max(p[x].back(),f[x]));
for(auto i : v[x]){
if(vi[i.ff] == 0){
ll y = p[x].back();
if(y == p[i.ff].back() + i.ss) y = p[x][sz(p[x]) - 2];
f[i.ff] = (max(y,f[x]) + i.ss);
df(i.ff);
}
}
return;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
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 = 1e9;
df(i);
v1.push_back(mn);
}
}
sort(v1.begin(), v1.end());
ll k = v1[sz(v1) - 1];
if(sz(v1) >= 2) k = max(k,v1[sz(v1) - 1] + l + v1[sz(v1) - 2]);
if(sz(v1) >= 3) k = max(k, v1[sz(v1) - 3] + l*2 + v1[sz(v1) - 2]);
return k;
}
