#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
pair<int,int> dfs(int a, int ant, int d, vector<vector<pair<int,int>>>& v, vector<pair<int,int>>& pais, vector<bool>& vis) {
pair<int,int> resp = {d,a};
pais[a] = {d,ant};
vis[a] = 1;
for (auto [c,b] : v[a]) {
if (b != ant) {
resp = max(resp,dfs(b,a,d+c,v,pais,vis));
}
}
return resp;
}
pair<int,int> centro(int a, int b, int d, vector<pair<int,int>>& pais) {
int val = d;
while (pais[a].first > d/2) {
val = pais[a].first;
a = pais[a].second;
}
return {d,max(val,d - pais[a].first)};
}
int travelTime(int n, int m, int l, int inp1[], int inp2[], int inpval[]) {
vector<vector<pair<int,int>>> v(n);
vector<pair<int,int>> pais(n,{0,-1});
vector<bool> vis(n,0);
for (int i = 0; i < m; i++) {
int a = inp1[i], b = inp2[i], c = inpval[i];
v[a].push_back({c,b});
v[b].push_back({c,a});
}
vector<pair<int,int>> diam;
int resp = 0, len = 0;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
len++;
auto [_,a] = dfs(i,-1,0,v,pais,vis);
auto [d,b] = dfs(a,-1,0,v,pais,vis);
diam.push_back(centro(b,a,d,pais));
resp = max(resp,diam[len-1].first);
}
}
sort(diam.begin(),diam.end());
if (len > 2) {
resp = max(resp,diam[len-2].second + diam[len-3].second + 2*l);
}
if (len > 1) {
resp = max(resp, diam[len-1].second + diam[len-2].second + l);
}
return resp;
}
