#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
long long ww,lv[300005],lv1[300005],mx,vert,fix[300005],x1,x2,x,y,anss;
std::vector <long long> v[300005],vv,ans;
map < pair <long long, long long > , long long > mp;
void dfs(int a, int p)
{
fix[a]=1;
if (ww==1) vv.push_back(a);
if (p!=-1)
lv[a]=lv[p]+mp[{a,p}];
else lv[a]=0;
if (lv[a]>mx)
{
vert=a;
mx=lv[a];
}
for (int i=0; i<v[a].size(); i++)
{
if (v[a][i]!=p)
{
dfs(v[a][i],a);
}
}
}
void dfs1(int a, int p)
{
if (p!=-1)
lv1[a]=lv1[p]+mp[{a,p}];
else lv1[a]=0;
for (int i=0; i<v[a].size(); i++)
{
if (v[a][i]!=p)
{
dfs1(v[a][i],a);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i=0; i<=1e5; i++)
v[i].clear();
ans.clear();
for (int i=0; i<M; i++)
{
mp[{A[i],B[i]}]=T[i];
mp[{B[i],A[i]}]=T[i];
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
for (int i=0; i<N; i++)
{
mx=0;
if (!fix[i])
{
vv.clear();
ww=1;
dfs(i,-1);
x1=vert;
ww=0;
mx=0;
dfs(x1,-1);
x2=vert;
dfs1(x2,-1);
x=1e9;
for (int j=0; j<vv.size(); j++)
{
anss=max(anss, lv[vv[j]]);
anss=max(anss, lv1[vv[j]]);
y=max(lv[vv[j]], lv1[vv[j]]);
x=min(x, y);
}
ans.push_back(x);
// cout<<x<<endl;
}
}
sort(ans.begin(), ans.end());
reverse(ans.begin(), ans.end());
if (ans.size()>=3)
{
anss=max(anss,ans[1]+ans[2]+2*L);
anss=max(anss, ans[0]+ans[1]+L);
return anss;
// cout<<anss<<endl;
}
if (ans.size()>=2)
{
anss=max(anss, ans[0]+ans[1]+L);
return anss;
// cout<<anss<<endl;
}
return 0;
}
