#include<bits/stdc++.h>
#include "dreaming.h"
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
int n,m,l,leader,bogdan;
bool used[maxn];
int dp[maxn];
struct c
{
int x,t;
};
vector<c> v[maxn];
vector<int> leaders,dps;
void dfs(int i)
{
if(v[leader].size()<v[i].size())
{
leader=i;
}
used[i]=1;
for(auto nb:v[i])
{
if(used[nb.x]==0)
{
dfs(nb.x);
}
}
}
void dfs1(int i,int par)
{
for(auto nb:v[i])
{
if(nb.x==par)
{
continue;
}
dfs1(nb.x,i);
dp[i]=max(dp[i],dp[nb.x]+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=1;i<=n;i++)
{
if(used[i]==0)
{
leader=i;
dfs(i);
leaders.push_back(leader);
}
}
for(auto i:leaders)
{
dfs1(i,0);
dps.push_back(dp[i]);
}
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);
}
