#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
struct edge
{
long long ver,dist;
edge(){};
edge(int vi, long long di)
{
ver = vi;
dist = di;
}
};
struct Point
{
int x,y,d;
Point(){};
Point(int xi, int yi, int di)
{
x = xi;
y = yi;
d = di;
}
};
int n;
vector<edge> g[MAXN];
long long sub[MAXN],used[MAXN];
long long mind,vut;
vector<long long> comp;
void clear_used()
{
for(int i = 0; i < n; i++) used[i] = 0;
}
void clear_g()
{
for(int i = 0; i < n; i++) g[i].clear();
}
void dfs_dp(int beg, long long gor)
{
used[beg] = 1;
long long maxch = max(sub[beg],gor);
vut = max(vut,maxch);
mind = min(mind,maxch);
long long fir = 0, sec = 0;
for(edge nb : g[beg])
{
if(!used[nb.ver])
{
if(nb.dist+sub[nb.ver] >= fir)
{
sec = fir;
fir = nb.dist+sub[nb.ver];
}
else if(nb.dist+sub[nb.ver] >= sec)
{
sec = nb.dist+sub[nb.ver];
}
}
}
for(edge nb : g[beg])
{
if(!used[nb.ver])
{
long long new_gor = gor;
if(nb.dist+sub[nb.ver] == fir) new_gor = max(new_gor,sec);
else new_gor = max(new_gor,fir);
new_gor += nb.dist;
dfs_dp(nb.ver,new_gor);
}
}
}
void dfs(int beg)
{
used[beg] = 1;
for(edge nb : g[beg])
{
if(!used[nb.ver])
{
dfs(nb.ver);
sub[beg] = max(sub[beg],sub[nb.ver]+nb.dist);
}
}
}
Point sp[90*MAXN];
int idx,lead[90*MAXN],br[90*MAXN];
bool cmp(Point p1, Point p2)
{
return p1.d<p2.d;
}
int find_lead(int x)
{
if(lead[x]==x) return x;
return lead[x] = find_lead(lead[x]);
}
void union1(int x, int y)
{
if(br[x]<br[y])
{
br[y] += br[x];
lead[x] = y;
}
else
{
br[x] += br[y];
lead[y] = x;
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
n = N;
for(int i = 0; i < M; i++)
{
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
for(int i = 0; i < N; i++) if(!used[i]) dfs(i);
clear_used();
for(int i = 0; i < N; i++)
{
if(!used[i])
{
mind = 1e9+5;
dfs_dp(i,0);
comp.push_back(mind);
}
}
idx = 0;
for(int i = 0; i < comp.size(); i++)
{
for(int j = i+1; j < comp.size(); j++)
{
sp[idx] = {i,j,comp[i]+comp[j]+L};
idx++;
}
}
clear_used();
clear_g();
for(int i = 0; i < comp.size(); i++)
{
lead[i] = i;
br[i] = 1;
}
sort(sp,sp+idx,cmp);
for(int i = 0; i < idx; i++)
{
int x = sp[i].x;
int y = sp[i].y;
x = find_lead(x);
y = find_lead(y);
if(x != y)
{
g[sp[i].x].push_back({sp[i].y,sp[i].d});
g[sp[i].y].push_back({sp[i].x,sp[i].d});
union1(x,y);
}
}
///
memset(sub,0,sizeof(sub));
for(int i = 0; i < comp.size(); i++) if(!used[i]) dfs(i);
clear_used();
long long ans = 0;
for(int i = 0; i < comp.size(); i++)
{
if(!used[i])
{
mind = 1e9+5;
dfs_dp(i,0);
ans = max(ans,mind);
}
}
return max(ans,vut);
}
