#include "dreaming.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
vector<pair<int,int>> adj[N];
int maxdep[N];
int dep[N];
bool vis[N];
void dfs(int v,int par){
vis[v] = 1;
for(auto u:adj[v]){
if(u.first == par)continue;
dep[u.first] = dep[v] + u.second;
dfs(u.first,v);
maxdep[v] = max(maxdep[v],maxdep[u.first] + u.second);
}
}
int mini,ans = 0;
void dfs1(int v,int par,int c){
vis[v] = 1;
multiset<int> s = {0};
for(auto u:adj[v]){
if(u.first == par)continue;
s.insert(maxdep[u.first] + u.second);
}
for(auto u:adj[v]){
if(u.first == par)continue;
s.erase(s.find(maxdep[u.first] + u.second));
dfs1(u.first,v,max(c,*s.rbegin()) + u.second);
s.insert(maxdep[u.first] + u.second);
}
ans = max(ans,max(c,maxdep[v]));
mini = min(mini,max(c,maxdep[v]));
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i = 0;i<m;i++){
a[i]++,b[i]++;
adj[a[i]].push_back({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
vector<int> v;
for(int i = 1;i<=n;i++){
if(!vis[i]){
dfs(i,0);
}
}
for(int i = 1;i<=n;i++){
vis[i] = 0;
}
for(int i = 1;i<=n;i++){
if(!vis[i]){
mini = 1e9;
dfs1(i,0,0);
v.push_back(mini);
}
}
sort(v.begin(),v.end());
for(int i = v.size()-2;i>=0;i--){
ans = max(ans,v[i] + v[v.size() - 1] + l);
v[v.size()-1] = max(v[v.size()-1],v[i] + l);
}
return ans;
}
