#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
vector < pair < int, int > > adj[maxn];
int used[maxn], depth[maxn];
int max_depth[maxn];
void calc(int v, int p)
{
used[v] = 1;
max_depth[v] = 0;
for (pair < int, int > nb : adj[v])
{
int u = nb.first;
if (u == p)
continue;
depth[u] = depth[v] + nb.second;
calc(u, v);
max_depth[v] = max(max_depth[v], max_depth[u] + nb.second);
}
}
int dist;
void dfs(int v, int p, int lon)
{
//cout << "dfs " << v << " " << p << " " << lon << endl;
int val = lon, sec = 0;
for (pair < int, int > nb : adj[v])
{
int u = nb.first;
if (u == p)
continue;
if (max_depth[u] + nb.second > val)
{
sec = val;
val = max_depth[u] + nb.second;
}
else if (max_depth[u] + nb.second > sec)
{
sec = max_depth[u] + nb.second;
}
}
//cout << val << " " << sec << endl;
dist = min(dist, val);
if (val == lon)
return;
for (pair < int, int > nb : adj[v])
{
int u = nb.first;
if (u == p)
continue;
if (val == max_depth[u] + nb.second)
{
dfs(u, v, sec + nb.second);
return;
}
}
}
int find_distance(int v)
{
calc(v, -1);
dist = 2e9;
dfs(v, -1, 0);
return dist;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i = 0; i < M; i ++)
{
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
//cout << find_distance(1) << endl;
//exit(0);
vector < ll > values;
for (int i = 0; i < N; i ++)
{
if (!used[i])
values.push_back(find_distance(i));
}
//for (int cur : values)
//cout << cur << " ";
//cout << endl;
sort(values.begin(), values.end());
int sz = values.size();
ll res = values[sz - 1] + values[sz - 2] + L;
if (sz >= 3)
res = max(res, values[sz - 2] + values[sz - 3] + 2 * L);
return res;
}
