#include <vector>
#include <algorithm>
#include <queue>
#include "dreaming.h"
using namespace std;
int const N=1e5+10;
vector<pair<int,int>>nei[N]={};
vector<int>heads;
int vis[N]={};
int cost[N]={};
void dfs(int n)
{
vis[n]=1;
for (auto [i,w]:nei[n])
{
if (!vis[i])
{
cost[n]+=w;
dfs(i);
cost[n]+=cost[i];
}
}
}
vector<pair<int,int>>cur={};
bool w1=0;
void getroot(int n,int pa,int root)
{
int f=cost[root]-cost[n];
for (auto [i,w]:nei[n])
{
if (i!=pa)
{
f=max(f,cost[i]+w);
getroot(i,n,root);
}
else
f=max(f,cost[root]-cost[n]);
}
cur.push_back({f,n});
}
void bfs(int n)
{
queue<pair<int,int>>Q;
Q.push({n,-1});
while (Q.size())
{
int n,m;
tie(n,m)=Q.front();
Q.pop();
for (auto [i,w]:nei[n])
{
if (i!=m)
{
cost[i]=cost[n]+w;
Q.push({i,n});
}
}
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
int f=0;
for (int i=0;i<m;i++)
{
f+=t[i];
nei[a[i]].push_back({b[i],t[i]});
nei[b[i]].push_back({a[i],t[i]});
}
for (int i=0;i<n;i++)
{
if (!vis[i])
{
heads.push_back(i);
dfs(i);
}
}
for (int i=0;i<n;i++)
vis[i]={};
vector<pair<int,int>>new_head;
for (auto i:heads)
{
getroot(i,-1,i);
sort(begin(cur),end(cur));
new_head.push_back(cur[0]);
cur={};
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
for (int i=1;i<new_head.size();i++)
{
nei[new_head[0].second].push_back({new_head[i].second,l});
nei[new_head[i].second].push_back({new_head[0].second,l});
f+=l;
}
for (int i=0;i<n;i++)
cost[i]=0;
bfs(0);
w1=0;
new_head={};
for (int i=0;i<n;i++)
{
new_head.push_back({cost[i],i});
cost[i]=0;
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
w1=1;
bfs(new_head[0].second);
new_head={};
for (int i=0;i<n;i++)
{
new_head.push_back({cost[i],i});
cost[i]=0;
}
sort(begin(new_head),end(new_head));
reverse(begin(new_head),end(new_head));
return new_head[0].first;
}
