#include "dreaming.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include "assert.h"
#define int int64_t
using namespace std;
struct graph
{
int n;
vector<vector<pair<int,int>>> adjlist;
vector<int> comp;
vector<int> dist;
int nrcomp = 0;
void compdfs(int curr, int par, int c)
{
comp[curr] = c;
for (auto p : adjlist[curr])
{
int next = p.first;
if (next == par) continue;
compdfs(next, curr, c);
}
}
void distdfs(int curr, int par, int d)
{
dist[curr] = max(dist[curr], d);
for (auto p : adjlist[curr])
{
int next = p.first;
int w = p.second;
if (next == par) continue;
assert(next != -1);
distdfs(next, curr, d + w);
}
}
void print()
{
for (int i = 0; i < n; i++)
{
if (i < 10) cout << " ";
cout << i << " ";
}
cout << "\n";
for (auto i : dist)
{
if (i < 10) cout << " ";
cout << i << " ";
}
cout << "\n";
}
int calc(int l)
{
dist.resize(n, -1);
comp.resize(n, -1);
for (int i = 0; i < n; i++)
{
if (comp[i] == -1)
{
compdfs(i, -1, nrcomp);
nrcomp++;
}
}
for (int i = 0; i < n; i++)
{
if (dist[i] < 0)
{
distdfs(i, -1, 0);
}
}
vector<int> md(nrcomp, -1);
vector<int> mv(nrcomp, -1);
for (int i = 0; i < n; i++)
{
if (dist[i] > md[comp[i]])
{
md[comp[i]] = dist[i];
mv[comp[i]] = i;
}
}
for (auto i : mv) distdfs(i, -1, 0);
md.assign(nrcomp, -1);
mv.assign(nrcomp, -1);
for (int i = 0; i < n; i++)
{
if (dist[i] > md[comp[i]])
{
md[comp[i]] = dist[i];
mv[comp[i]] = i;
}
}
for (auto i : mv) distdfs(i, -1, 0);
md.assign(nrcomp, 1e12);
for (int i = 0; i < n; i++)
{
if (dist[i] < md[comp[i]])
{
md[comp[i]] = dist[i];
}
}
sort(md.begin(), md.end());
if (nrcomp == 1) return md.back();
int mmax = md[nrcomp - 1] + md[nrcomp - 2] + l;
if (nrcomp != 2) mmax = max(md[nrcomp - 2] + md[nrcomp - 3] + 2*l, mmax);
return mmax;
}
};
signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[])
{
graph g;
g.n = N;
g.adjlist.resize(N);
for (int i = 0; i < M; i++)
{
g.adjlist[A[i]].emplace_back(B[i], T[i]);
g.adjlist[B[i]].emplace_back(A[i], T[i]);
}
return g.calc(L);
}
