#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> gri;
vector<int> dis = {0,0,0};
vector<int> dep;
vector<int> used;
int jic = 0;
int y;
int dfs(int x, int p){
used[x] = 1;
int s = 0;
for(int i = 0; i < (int)gri[x].size(); ++i){
int z = 0;
if(gri[x][i].first != p)z = dfs(gri[x][i].first,x)+gri[x][i].second;
dep.push_back(z);
s+=z;
}
return s;
}
void find(int ind){
if(!gri[ind].size()){dis.push_back(0);return;}
dep.clear();
y = dfs(ind,ind);
jic = max(jic,y);
int best = INT_MAX;
for(int i = 0; i < (int)dep.size(); ++i){
best = min(best, max(y-dep[i],dep[i]));
}
dis.push_back(best);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
used.resize(N,0);
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] && gri[i].size() == 1){
find(i);
}
}
sort(dis.rbegin(),dis.rend());
return max(jic,max(dis[0]+L+dis[1],dis[1]+2*L+dis[2]));
}
