#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#define ll long long
#define f first
#define s second
typedef pair<int,int> pi;
int INF = 1e9+7;
ll N,E,L;
int visited[100010];
vector <pi> adjlist[100010];
int dist1[100010], dist2[100010];
int camefrom[100010];
vector <ll> centerboi; //Stores minimum radius for each tree
int counter=-1;
vector <int> whoishere;
vector <ll> diameters;
void dfsf(int x, int p) {
whoishere.push_back(x);
visited[x] = 1;
for (auto i: adjlist[x]) {
if (i.f != p) {
dist1[i.f] = dist1[x] + i.s;
dfsf(i.f,x);
}
}
}
void dfss(int x, int p) {
camefrom[x] = p;
for (auto i: adjlist[x]) {
if (i.f != p) {
dist2[i.f] = dist2[x] + i.s;
dfss(i.f,x);
}
}
}
void trace(int x,int endn) {
//~ cout << x << " " << endn << " " << counter << "\n";
//~ cout << x << " " << dist2[x] << " " << endn << " " << dist2[endn] << "\n";
if (max(dist2[x],dist2[endn]-dist2[x]) < centerboi[counter]) {
centerboi[counter] = max(dist2[x],dist2[endn]-dist2[x]);
}
//~ cout << centerboi[counter] << "\n";
if (camefrom[x] != -1) trace(camefrom[x],endn);
}
void rootat(int x) {
counter++;
whoishere.clear();
dfsf(x,-1);
int start = x;
for (auto i: whoishere) {
if (dist1[i] > dist1[start]) start = i;
}
dfss(start,-1);
int endn = start;
for (auto i: whoishere) {
if (dist2[i] > dist2[endn]) endn = i;
}
diameters.push_back(dist2[endn]);
centerboi.push_back(INF);
trace(endn,endn);
//~ cout << counter << " " << start << " " << endn << " " << centerboi[counter] << "\n";
}
int travelTime(int _N, int M, int _L, int A[], int B[], int T[]) {
N = _N;
E = M;
L = _L;
for (int i =0;i <E;i++) {
int a = A[i];
int b = B[i];
int w = T[i];
adjlist[a].push_back(pi(b,w));
adjlist[b].push_back(pi(a,w));
}
for (int i =0;i<N;i++) if (!visited[i]) rootat(i);
sort(centerboi.begin(),centerboi.end(),greater<int>());
//~ cout << "\n";
//~ for (auto i:centerboi) {
//~ cout << i << "\n";
//~ }
ll ans = 0;
if (counter >= 1)
ans = max(ans,centerboi[0] + centerboi[1] + L);
if (counter >= 2)
ans = max(ans, centerboi[1] + centerboi[2] + 2*L);
for (auto i: diameters) {
ans = max(ans,i);
}
return ans;
}
