#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pb push_back
#define REP(i,a,b) for(int i=a;i<b;i++)
int dist[121010], par[121010]; // 42 days to go, 42 lines of code.
vector<int> cc;
vector<ii> adj[121010];
void dfs(int x, int p, bool ins) {
par[x]=p; if(ins) cc.pb(x);
for(auto i: adj[x]) if(i.fi!=p) {dist[i.fi]=dist[x]+i.se; dfs(i.fi,x,ins);}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<int> cenTimes; int maxD=0;
REP(i,0,M) {
adj[A[i]].pb(ii(B[i],T[i]));
adj[B[i]].pb(ii(A[i],T[i]));
}
REP(i,0,N) if(dist[i]==0) {
cc.clear();
dfs(i,-1,1);
ii far=ii(0,0);
for(auto j: cc) far=max(far,ii(dist[j],j));
int pt1=far.se;
dist[pt1]=0;
dfs(pt1,-1,0);
far=ii(0,0);
for(auto j: cc) far=max(far,ii(dist[j],j));
maxD=max(maxD,far.fi);
int cnt=0;
while(far.se!=pt1&&dist[far.se]+dist[par[far.se]]>far.fi) far.se=par[far.se];
cenTimes.pb(max(dist[far.se],far.fi-dist[far.se]));
dist[pt1]=420;
}
sort(cenTimes.begin(),cenTimes.end(),greater<int>());
if(cenTimes.size()>=2) maxD=max(maxD,cenTimes[0]+cenTimes[1]+L);
if(cenTimes.size()>=3) maxD=max(maxD,cenTimes[1]+cenTimes[2]+2*L);
return maxD;
}
