#include "dreaming.h"
#include <vector>
#include <iostream>
#include <algorithm>
#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;
pair<int,int> compdfs(int curr, int par, int c)
{
comp[curr] = c;
int mmax = 0;
int mver = curr;
for (auto p : adjlist[curr])
{
int next = p.first;
int w = p.second;
if (next == par) continue;
auto pn = compdfs(next, curr, c);
pn.second += w;
if (pn.second > mmax)
{
mmax = pn.second;
mver = pn.first;
}
}
return {mver, mmax};
}
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;
distdfs(next, curr, d + w);
}
}
int calc(int l)
{
dist.resize(n, -1);
comp.resize(n, -1);
for (int i = 0; i < n; i++)
{
if (comp[i] == -1)
{
comp[i] = nrcomp;
auto rp = compdfs(i, -1, nrcomp);
distdfs(rp.first, -1, 0);
nrcomp++;
}
}
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 j : mv)
{
distdfs(j, -1, 0);
}
md.assign(nrcomp, (int)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 <= 2)
{
int ssum = 0;
for (auto i : md) ssum += i;
if (nrcomp == 2) ssum += l;
return ssum;
}
return max(md[nrcomp - 1] + md[nrcomp - 2] + l, md[nrcomp - 2] + md[nrcomp - 3] + 2*l);
}
void print()
{
for (int i = 0; i < n; i++)
{
if (i < 10) cout << " ";
cout << i << " ";
}
cout << "\n";
for (auto i : comp)
{
if (i < 10) cout << " ";
cout << i << " ";
}
cout << "\n";
for (auto i : dist)
{
if (i < 10) cout << " ";
cout << i << " ";
}
cout << "\n";
}
};
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);
}
