#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef pair<int,int> pii;
#define fi first
#define se second
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int ff[SZ]; Edgc
int gf(int x) {return (~ff[x])?ff[x]=gf(ff[x]):x;}
void uni(int a,int b)
{
a=gf(a),b=gf(b);
if(a==b) throw "GG";
ff[a]=b;
}
int ca=0;
pii mx;
vector<int> ve;
int fa[SZ],fe[SZ],d1[SZ],d2[SZ],*op;
void dfs(int x,int d=0)
{
ve.pb(x);
op[x]=d; mx=max(mx,pii(d,x));
for esb(x,e,b) if(b!=fa[x])
fa[b]=x,fe[b]=vc[e],dfs(b,d+vc[e]);
}
int work(int t)
{
auto g=ve;
mx=pii(-1,0);
ve.clear();
fa[t]=-1; op=d1; dfs(t);
ca=max(ca,mx.fi);
int u=mx.se;
mx=pii(-1,0);
ve.clear();
fa[u]=-1; op=d1; dfs(u);
int v=mx.se;
ve.clear();
fa[v]=-1; op=d2; dfs(v);
ca=max(ca,mx.fi);
int aa=mx.fi;
for(auto g:ve)
aa=min(aa,max(d1[g],d2[g]));
return aa;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
ca=0;
memset(ff,-1,sizeof ff);
for(int i=0;i<M;++i)
adde(A[i],B[i],T[i]),uni(A[i],B[i]);
vector<int> v;
for(int i=0;i<N;++i)
if(gf(i)==i) v.pb(work(i));
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
for(int i=1;i<v.size();++i) v[i]+=L;
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if(v.size()>=2) ca=max(ca,v[0]+v[1]);
return ca;
}
