#include "dreaming.h"
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
///#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
const int inf = 1e9;
const int maxn = 1e5+10;
const int mod = 1e9+7;
vector<pii> g[maxn];
bool mark[maxn];
vector<ll> fel;
int par[maxn], V;
ll h[maxn];
void dfs(int v)
{
if(h[v] > h[V]) V = v;
mark[v] = 1;
for(auto e : g[v])
{
int u = e.F, w = e.S;
if(u != par[v])
{
par[u] = v;
h[u] = h[v] + w;
dfs(u);
}
}
}
/*int A[8] = {0, 8, 2, 5, 5, 1, 1, 10};
int B[8] = {8, 2, 7, 11, 1, 3, 9, 6};
int T[8] = {4, 2, 4, 3, 7, 1, 5, 3};*/
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for(int i = 0; i < M; i++)
{
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
ll ANS = 0;
for(int v = 0; v < N; v++)
if(!mark[v])
{
V = v;
dfs(v);
int X = V;
V = X;
h[X] = 0; par[X] = 0;
dfs(X);
int Y = V;
ll ans = h[Y];
while(V != X)
{
ans = min(ans, max(h[Y]-h[V],h[V]));
V = par[V];
}
fel.push_back(ans);
ANS = max(ANS,h[Y]);
}
sort(fel.begin(), fel.end());
if((int)fel.size() == 1) return ANS;
if((int)fel.size() == 2) return max(fel[0] + fel[1] + L, ANS);
//cout<< ANS <<" ";
int MM = (int)fel.size();
return max({fel[MM-1] + fel[MM-2] + L, fel[MM-2] + fel[MM-3] + 2 * L, ANS});
}
/*
signed main()
{
//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<< travelTime(12, 8, 2);
}*/
