#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
const int maxn=1e5+10;
vector<vector<pi>> graph(maxn);
vector<pi> dst1(maxn,{0,-1}),dst2(maxn,{0,-1});
vi seen(maxn,0);
int dia=0;
multiset<int> mx;
void dfs(int cur, int prev) {
seen[cur]=1;
for (auto [to,c]:graph[cur]) {
if (to==prev) {
continue;
}
dfs(to,cur);
if (dst1[to].fi+c>dst1[cur].fi) {
dst2[cur]=dst1[cur];
dst1[cur]={dst1[to].fi+c,to};
}
else if (dst1[to].fi+c>dst2[cur].fi) {
dst2[cur]={dst1[to].fi+c,to};
}
}
dia=max(dia,dst1[cur].fi+dst2[cur].fi);
}
int dfs2(int cur, int prev) {
int mn=dst1[cur].fi;
for (auto [to,c]:graph[cur]) {
if (to==prev) {
continue;
}
int t;
if (dst1[cur].se!=to) {
t=dst1[cur].fi+c;
}
else {
t=dst2[cur].fi+c;
}
if (t>dst1[to].fi) {
dst2[to]=dst1[to];
dst1[to]={t,cur};
}
else if (t>dst2[to].fi) {
dst2[to]={t,cur};
}
mn=min(mn,dfs2(to,cur));
}
return mn;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for (int i=0; i<m; i++) {
graph[a[i]].pb({b[i],t[i]});
graph[b[i]].pb({a[i],t[i]});
}
for (int i=0; i<n; i++) {
if (!seen[i]) {
dfs(i,i);
mx.insert(dfs2(i,i));
if (mx.size()>3) {
mx.extract(mx.begin());
}
}
}
if (mx.size()==3) {
dia=max(dia,*mx.begin()+*next(mx.begin())+2*l);
dia=max(dia,*next(mx.begin())+*next(next(mx.begin()))+l);
}
else if (mx.size()==2) {
dia=max(dia,*mx.begin()+*next(mx.begin())+l);
}
return dia;
}
