#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> al;
typedef vector<int> vi;
typedef vector<vi> vvi;
ii dfa(int u, int p, al& g, vii& pa) {
ii res = {u,0};
for(int i=0;i<g[u].size();i++) {
int v = g[u][i].first;
int dist = g[u][i].second;
if(v == p) {
continue;
}
pa[v] = {u,dist};
ii dv = dfa(v,u,g,pa);
if(dv.second+dist > res.second) {
res = {dv.first,dv.second+dist};
}
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
al g;
g.assign(N,vii());
for(int i=0;i<M;i++) {
int a = A[i];
int b = B[i];
g[a].push_back({b,T[i]});
g[b].push_back({a,T[i]});
}
vii pa(N,{-1,-1});
vi rep;
vii dia;
int res = 0;
for(int i=0;i<N;i++) {
if(pa[i].first == -1) {
ii va = dfa(i,i,g,pa);
int mv = va.first;
pa[mv] = {mv,0};
ii vb = dfa(mv,mv,g,pa);
rep.push_back(mv);
dia.push_back(vb);
res = max(res,vb.second);
}
}
vi wa;
for(int i=0;i<rep.size();i++) {
int u = dia[i].first;
int da = 0;
int db = dia[i].second;
int dv = db;
while(pa[u].first != u) {
da += pa[u].second;
db -= pa[u].second;
u = pa[u].first;
dv = min(dv,max(da,db));
}
wa.push_back(dv);
}
sort(wa.rbegin(),wa.rend());
res = max(res,wa.front());
if(wa.size() > 1) {
res = max(res,wa[0]+wa[1]+L);
}
if(wa.size() > 2) {
res = max(res,wa[1]+wa[2]+2*L);
}
return res;
}
