#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define oo 1e9
const int MAX = 1e5 + 5;
vector<pii> g[MAX];
int n, m;
bool visited[MAX];
pii dfs(int node, int p){
visited[node] = 1;
pii ans = {0, node};
for(auto to : g[node]){
if(to.first == p) continue;
pii nw = dfs(to.first, node);
nw.first += to.second;
if(ans.first < nw.first) ans = nw;
}
return ans;
}
int biggestDist[MAX];
int smallestDist = oo;
int finalAns = 0;
void dfs2(int node, int p, int h){
if(biggestDist[node] == -1){
biggestDist[node] = h;
}
else{
smallestDist = min(smallestDist, max(biggestDist[node], h));
}
for(auto to : g[node]){
if(to.first == p) continue;
dfs2(to.first, node, h + to.second);
}
}
vector<int> v;
void findDia(int node){
int a = dfs(node, node).second;
int b = dfs(a, a).second;
dfs2(a, a, 0);
finalAns = max(finalAns, biggestDist[b]);
dfs2(b, b, 0);
v.push_back(smallestDist);
smallestDist = oo;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
memset(biggestDist, -1, sizeof(biggestDist));
n = N;
m = M;
for(int i = 0; i < m; i++){
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
for(int i = 0; i < n; i++){
if(!visited[i]){
findDia(i);
}
}
sort(v.begin(), v.end());
if(v.size() == 1){
return finalAns;
}
if(v.size() == 2){
return max(finalAns, (v[v.size() - 1] + L + v[v.size() - 2]));
}
return max(max( (v[v.size() - 1] + L + v[v.size() - 2]) ,
(v[v.size() - 2] + 2 * L + v[v.size() - 3]) ), finalAns);
}
