#include "dreaming.h"
#include <vector>
#include <iostream>
#include <algorithm>
#define X first
#define Y second
using namespace std;
const int MAXN = 100100;
int dp1[MAXN], dp2[MAXN];
vector<pair<int, int>> v[MAXN];
int n, m, l;
int used[MAXN];
int ba;
vector<int> vr;
void dfs1(int beg,int par)
{
used[beg]=1;
for(pair<int,int> nb:v[beg])
{
if(nb.X==par)continue;
dfs1(nb.X,beg);
dp1[beg]=max(dp1[beg],dp1[nb.X]+nb.Y);
}
}
void dfs2(int beg,int par)
{
int ans=dp2[beg];
vector<pair<int,int>> kids;
for(pair<int,int> nb:v[beg])
{
if(nb.X==par)continue;
ans=max(ans,nb.Y+dp1[nb.X]);
kids.push_back({nb.X,nb.Y});
}
ba=min(ba,ans);
int sz=kids.size();
if(sz==0)return;
vector<int> pref(sz),sufx(sz);
pref[0]=kids[0].Y+dp1[kids[0].X];
for(int i=1;i<sz;i++)
{
pref[i]=max(pref[i-1],kids[i].Y+dp1[kids[i].X]);
}
sufx[sz-1]=kids[sz-1].Y+dp1[kids[sz-1].X];
for(int i=sz-2;i>=0;i--)
{
sufx[i]=max(sufx[i+1],kids[i].Y+dp1[kids[i].X]);
}
for(int i=0;i<sz;i++)
{
int nb=kids[i].X;
int val=dp2[beg];
if(i-1>=0)val=max(val,pref[i-1]);
if(i+1<sz)val=max(val,sufx[i+1]);
dp2[nb]=kids[i].Y+val;
dfs2(nb,beg);
}
}
void check(int i)
{
if(used[i])return;
ba=1e9;
dfs1(i,0);
dfs2(i,0);
vr.push_back(ba);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
vr.clear();
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++)
check(i);
sort(vr.rbegin(),vr.rend());
if(vr.size()==1)return vr[0];
if(vr.size()==2)return vr[0]+vr[1]+l;
return max(vr[0]+vr[1]+l,vr[1]+l+vr[2]+l);
}
