#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
bool viz[100005];
vector<pair<int, int>> v[100005];
pair<int, int> dfs(int p, int par)
{
viz[p]=true;
pair<int, int> ans={0, p};
for(auto it : v[p])
{
if(it.first == par)
continue;
pair<int, int> nans = dfs(it.first, p);
ans = max(ans, {nans.first + it.second, nans.second});
}
return ans;
}
bool calcPath(int p, int par, int b, vector<int> &e)
{
if(p == b)
return true;
for(auto it : v[p])
{
if(it.first == par)
continue;
if(calcPath(it.first, p, b, e))
{
e.push_back(it.second);
return true;
}
}
return false;
}
int solve(int p)
{
int a = dfs(p, 0).second;
int b = dfs(a, 0).second;
vector<int> e;
calcPath(a, 0, b, e);
if(e.empty())
return 0;
int ans=1e9, sumP=0, sumS=0;
for(int it : e)
sumS += it;
for(int it : e)
{
sumP += it;
sumS -= it;
ans=min(ans, max(sumP, sumS));
}
return ans;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
for(int i=0;i<m;i++)
{
v[a[i]+1].push_back({b[i]+1, t[i]});
v[b[i]+1].push_back({a[i]+1, t[i]});
}
int nr=0;
int ans1=0, ans2=0, ans3=0;
for(int i=1;i<=n;i++)
{
if(!viz[i])
{
nr++;
int nans = solve(i);
if(nans>ans1)
{
ans3=ans2;
ans2=ans1;
ans1=nans;
}
else if(nans > ans2)
{
ans3=ans2;
ans2=nans;
}
else if(nans > ans3)
{
ans3=nans;
}
}
}
if(nr>2)
return max(l+ans1+ans2, 2*l+ans2+ans3);
if(nr == 2)
return l+ans1+ans2;
return 0;
}
