#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int n,m,k;
vector<pair<int,int> > v[100001];
int c[100001],num;
int in;
int r[100001];
int lp[1000001];
int furt[100001],ver[100001];
int sfurt[100001];
int act[100001];
void prec(int i,int p)
{
c[i]=num;
for(int j=0; j<v[i].size(); j++)
{
int nb=v[i][j].first;
if(nb!=p)
{
lp[nb]=v[i][j].second;
prec(nb,i);
}
}
}
int up[100001];
int minn[100001];
int dfs(int i,int p)
{
if(v[i].size()==1&&p||v[i].size()==0)return 0;
int curr=0,f1=0,f2=0;
for(int j=0; j<v[i].size(); j++)
{
int nb=v[i][j].first;
if(nb==p)continue;
int f=dfs(nb,i)+v[i][j].second;
if(furt[i]<f)
{
sfurt[i]=furt[i];
furt[i]=f;
ver[i]=nb;
}
else sfurt[i]=max(sfurt[i],f);
curr=max(curr,f);
if(f>=f1)
{
f2=f1;
f1=f;
}
else if(f>=f2)
{
f2=f;
}
}
in=max(in,f1+f2);
//cout<<i-1<<": "<<furt[i]<<" "<<ver[i]<<" "<<sfurt[i]<<endl;
//cout<<i<<" - "<<curr<<endl;
return curr;
}
void up_(int i,int p)
{
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j].first;
if(nb==p)continue;
int add=furt[i];
if(ver[i]==nb)add=sfurt[i];
up[nb]=lp[nb]+max(up[i],add);
up_(nb,i);
//cout<<nb-1<<" // "<<up[nb]<<endl;
}
}
int solve()
{
for(int i=1; i<=num; i++)
{
minn[i]=1e9;
//cout<<"** "<<r[i]-1<<endl;
dfs(r[i],0);
up_(r[i],0);
}
for(int i=1; i<=n; i++)
{
//cout<<c[i]<<" "<<i<<" "<<dfs(i,0)<<endl;
minn[c[i]]=min(minn[c[i]],max(furt[i],up[i]));
}
sort(minn+1,minn+num+1);
if(num>=3)in=max(in,minn[num-1]+minn[num-2]+2*k);
if(num>=2)in=max(in,minn[num-1]+minn[num]+k);
return in;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
n=N;
m=M;
k=L;
//cout<<n<<" "<<m<<" "<<k<<endl;
for(int i=0;i<m;i++)
{
A[i]++;
B[i]++;
//cout<<A[i]<<" "<<B[i]<<" "<<T[i]<<endl;
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for(int i=1; i<=n; i++)
if(!c[i])
{
num++;
r[num]=i;
prec(i,0);
}
return solve();
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
