#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> gri;
vector<pair<int,int>> b1, b2;
vector<int> dis, used;
int jic = 0, mmm;
void dfs1(int x, int p){
used[x] = 1;
for(int i = 0; i < (int)gri[x].size(); ++i){
if(gri[x][i].first == p)continue;
dfs1(gri[x][i].first,x);
b2[x] = max(b2[x], {b1[gri[x][i].first].first+gri[x][i].second,gri[x][i].first});
if(b1[x] < b2[x])swap(b1[x],b2[x]);
}
}
void dfs2(int x, int p, int d){
used[x] = 1;
int y = max(b1[x].first,d);
mmm = min(mmm,y);
jic = max(jic,y);
for(int i = 0; i < gri[x].size(); ++i){
if(gri[x][i].first == p)continue;
if(gri[x][i].first == b1[x].second)dfs2(gri[x][i].first,x,max(b2[x].first,d)+gri[x][i].second);
else dfs2(gri[x][i].first,x,y+gri[x][i].second);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
if(N == 1)return 0;
if(N == 2)return (M ? T[0] : L);
used.resize(N,0);
b1.resize(N);
b2.resize(N);
gri.resize(N);
for(int i = 0; i < M; ++i){
gri[A[i]].push_back({B[i],T[i]});
gri[B[i]].push_back({A[i],T[i]});
}
for(int i = 0; i < N; ++i){
if(!used[i] && (int)gri[i].size() <= 1){
dfs1(i,i);
}
}
used.clear();
used.resize(N,0);
for(int i = 0; i < N; ++i){
if(!used[i] && (int)gri[i].size() <= 1){
mmm = INT_MAX;
dfs2(i,i,0);
dis.push_back(mmm);
}
}
sort(dis.rbegin(), dis.rend());
if(dis.size() >= 3){
return max(jic,max(dis[0]+L+dis[1],dis[1]+dis[2]+2*L));
}
if(dis.size() == 2){
return max(jic,dis[0]+L+dis[1]);
}
return jic;
}
