#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include "dreaming.h"
using namespace std;
const int NMAX=1e5;
vector <pair <int, int>> vec[NMAX+5];
vector <pair <int, int>> comp;
int viz[NMAX+5], root, diameter, radius, depth[NMAX+5];
void dfs (int nod, int tatal, int d, bool dif)
{
viz[nod]=1;
if (d >= diameter)
{
diameter = d;
root = nod;
}
if (dif)
{
radius=min (radius, max(d, depth[nod]));
}
else depth[nod] = d;
for (auto adj : vec[nod])
{
if (adj.first==tatal)
continue;
dfs (adj.first, nod, d+adj.second, dif);
}
}
int travelTime (int n, int m, int l, int *a, int *b, int *c)
{
int ret=0;
for (int i=0;i<m;i++)
{
vec[a[i]].push_back ({b[i], c[i]});
vec[b[i]].push_back ({a[i], c[i]});
}
for (int i=0;i<n;i++)
{
if (viz[i])
continue;
diameter=0;
radius=2e9;
dfs (i, -1, 0, 0);
dfs (root, -1, 0, 0);
dfs (root, -1, 0, 1);
comp.push_back ({radius, diameter});
}
sort (comp.begin(), comp.end(), greater <pair <int, int>> ());
ret=max (ret, comp[0].second);
if (comp.size()>=2) ret=max (ret, comp[0].first+comp[1].first+l);
if (comp.size()>=3) ret=max (ret, comp[1].first+comp[2].first+2*l);
return ret;
}
