#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e5 + 5;
vector<int> dia, mn, nodes;
vector<pair<int,int>> v[Nmax];
int dist[3][Nmax];
bool used[Nmax];
void dfs(int node, int t, int dad = -1)
{
if(!t) nodes.push_back(node), used[node] = 1;
for(auto it : v[node])
if(it.first != dad)
{
dist[t][it.first] = dist[t][node] + it.second;
dfs(it.first, t, node);
}
}
void solve_comp(int root)
{
nodes.clear();
dfs(root, 0);
int x = root;
for(auto i : nodes)
if(dist[0][x] < dist[0][i]) x = i;
dfs(x, 1);
int y = x;
for(auto i : nodes)
if(dist[1][y] < dist[1][i]) y = i;
dfs(y, 2);
int best = 1e9;
for(auto i : nodes)
if(dist[1][i] + dist[2][i] == dist[1][y])
best = min(best, max(dist[1][i], dist[2][i]));
dia.push_back(dist[1][y]);
mn.push_back(best);
}
int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
int ans = 0;
int i;
for(i=0; i<m; ++i)
{
v[A[i]].push_back({B[i], T[i]});
v[B[i]].push_back({A[i], T[i]});
}
for(i=0; i<n; ++i)
if(!used[i]) solve_comp(i);
for(auto it : dia)
ans = max(ans, it);
sort(mn.begin(), mn.end());
reverse(mn.begin(), mn.end());
if(mn.size() >= 2)
ans = max(ans, mn[0] + mn[1] + L);
if(mn.size() >= 3)
ans = max(ans, mn[1] + mn[2] + 2 * L);
return ans;
}
