#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define MAXN 100001
long long brkomp=0,timer=1,slucaj=-1;
vector<pair<long long,long long>> adj[MAXN];
long long komponenta[MAXN],dist[MAXN];
long long tin[MAXN],tout[MAXN],fenw[MAXN+1];
vector<long long> nodes[MAXN];
vector<long long> answers;
void dfs(long long node,long long pret)
{
komponenta[node]=brkomp;nodes[brkomp].push_back(node);
for (pair<long long,long long> par:adj[node])
{
int sled=par.first,w=par.second;if (sled==pret) continue;
dist[sled]=dist[node]+w;dfs(sled,node);
}
}
void dfs1(long long node,long long pret)
{
tin[node]=timer;timer++;
for (pair<long long,long long> par:adj[node])
{
int sled=par.first,w=par.second;if (sled==pret) continue;
dist[sled]=dist[node]+w;dfs1(sled,node);
}
tout[node]=timer-1;
}
void update(long long pos,long long val)
{
for (long long i=pos;i<=timer+1;i+=i&(-i)) fenw[i]+=val;
}
long long query(long long pos)
{
long long sum=0;
for (long long i=pos;i>0;i-=i&(-i)) sum+=fenw[i];
return sum;
}
void resi(long long komp,long long n)
{
long long maxdist=0,maxnode=nodes[komp][0];
for (long long node:nodes[komp])
{
if (dist[node]>maxdist) {maxdist=dist[node];maxnode=node;}
}
timer=1;dist[maxnode]=0;dfs1(maxnode,0);long long len=0,sol=len;
for (long long i=1;i<=timer+1;i++) fenw[i]=0;
for (long long node:nodes[komp]) {len=max(len,dist[node]);sol=len;}
for (long long node:nodes[komp])
{
if (dist[node]==len) update(tin[node],1);
}
for (long long node:nodes[komp])
{
long long value=max(dist[node],len-dist[node]);if (value>=sol) continue;
if (value==dist[node]) {sol=min(sol,value);continue;}
long long broj=query(tout[node])-query(tin[node]-1);if (broj>0) sol=min(sol,value);
}
slucaj=max(slucaj,len);answers.push_back(sol);
}
int travelTime(int n,int m,int l,int a[],int b[],int t[])
{
for (long long i=0;i<m;i++) {long long node1=a[i]+1,node2=b[i]+1,weight=t[i];adj[node1].push_back({node2,weight});adj[node2].push_back({node1,weight});}
for (long long node=1;node<=n;node++)
{
if (komponenta[node]==0) {brkomp++;dfs(node,0);}
}
for (long long komp=1;komp<=brkomp;komp++) resi(komp,n);
sort(answers.begin(),answers.end());long long ans=slucaj;
if (answers.size()!=1) ans=max(ans,answers[answers.size()-1]+answers[answers.size()-2]+l);
if (answers.size()>=3) ans=max(ans,answers[answers.size()-2]+answers[answers.size()-3]+2*l);
return ans;
}
