#include<bits/stdc++.h>
#include "dreaming.h"
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
int n,m,l;
int dp[maxn],f[maxn],s[maxn];
bool used[maxn];
long long minn;
struct c
{
int x,t;
};
vector<c> v[maxn];
vector<long long> dps;
void dfs(int i,int par)
{
used[i]=1;
int sm=0;
for(auto nb:v[i])
{
if(nb.x==par)
{
continue;
}
dfs(nb.x,i);
dp[i]=max(dp[i],dp[nb.x]+nb.t);
}
for(auto nb:v[i])
{
if(nb.x==par)
{
continue;
}
if(dp[nb.x]+nb.t==dp[i])
{
f[i]=nb.x;
}
else
{
if(dp[nb.x]+nb.t>s[i])
{
s[i]=dp[nb.x]+nb.t;
}
}
}
}
void dfs1(int i,int par,int t)
{
dp[i]=max(dp[i],t);
minn=min(minn,dp[i]*1LL);
for(auto nb:v[i])
{
if(nb.x==par)
{
continue;
}
if(nb.x==f[i])
{
dfs1(nb.x,i,max(t,s[i])+nb.t);
}
else
{
dfs1(nb.x,i,max(t,dp[i])+nb.t);
}
}
}
int travelTime(int N, int M, int L,int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
for(int i=0;i<m;i++)
{
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<n;i++)
{
if(used[i]==0)
{
minn=1e18;
dfs(i,-1);
dfs1(i,-1,0);
dps.push_back(minn);
}
}
sort(dps.begin(),dps.end());
reverse(dps.begin(),dps.end());
if(dps.size()==1)
{
return dps[0];
}
if(dps.size()==2)
{
return dps[0]+dps[1]+l;
}
return max(dps[0]+dps[1]+l,dps[1]+dps[2]+2*l);
}
