#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
using pii = pair<ll, ll>;
vector<vector<ll>> neighbours;
map<pair<ll,ll>,ll> edgeweight;
vector<vector<ll>>().swap(neighbours);
map<pair<ll,ll>,ll>().swap(edgeweight);
for(int i=0;i<n;i++)
{
neighbours.push_back(vector<ll>());
}
ll x,y,z;
for(int i=0;i<m;i++)
{
x=a[i];
y=b[i];
z=t[i];
neighbours[x].push_back(y);
neighbours[y].push_back(x);
edgeweight[make_pair(min(x,y),max(x,y))]=z;
}
unordered_set<ll> seen;
vector<ll> diameters({0,0});
vector<ll> radii({0,0,0});
for(int i=0;i<n;i++)
{
if(seen.find(i)==seen.end())
{
stack<ll> q;
vector<ll> path(n,-1);
vector<ll> weight(n,-1);
unordered_set<ll> currseen;
ll ep1,ep2,curr,total,currfurthest,currfurthestdistance;
q.push(i);
weight[i]=0;
currfurthest=-1;
currfurthestdistance=-1;
while(!q.empty())
{
curr = q.top();
q.pop();
seen.insert(curr);
for(auto neighbour:neighbours[curr])
{
if(seen.find(neighbour)==seen.end())
{
weight[neighbour]=weight[curr]+edgeweight[make_pair(min(neighbour,curr),max(neighbour,curr))];
q.push(neighbour);
}
}
}
for(int i=0;i<n;i++)
{
if(weight[i]>currfurthestdistance)
{
ep1=i;
currfurthestdistance=weight[i];
}
}
ep2=ep1;
currfurthestdistance=-1;
total=0;
vector<ll>(n,-1).swap(weight);
weight[ep1]=0;
unordered_set<ll>().swap(currseen);
stack<ll>({ep1}).swap(q);
while(!q.empty())
{
curr = q.top();
q.pop();
currseen.insert(curr);
for(auto neighbour:neighbours[curr])
{
if(currseen.find(neighbour)==currseen.end())
{
path[neighbour]=curr;
weight[neighbour]=weight[curr]+edgeweight[make_pair(min(neighbour,curr),max(neighbour,curr))];
q.push(neighbour);
}
}
}
for(int i=0;i<n;i++)
{
if(weight[i]>currfurthestdistance)
{
ep2=i;
currfurthestdistance=weight[i];
}
}
ll x,y,a,b;
x=max(weight[ep1],weight[ep2]-weight[ep1]);
y=min(weight[ep1],weight[ep2]-weight[ep1]);
ll p1=ep2;
while(p1!=ep1)
{
a=max(weight[p1],weight[ep2]-weight[p1]);
b=min(weight[p1],weight[ep2]-weight[p1]);
if(a<x)
{
x=a;
y=b;
}
p1=path[p1];
}
radii.push_back(x);
diameters.push_back(weight[ep2]);
}
}
sort(diameters.begin(),diameters.end(),greater<long long>());
sort(radii.begin(),radii.end(),greater<long long>());
/*
for(auto num:diameters)
{
cout << num << " ";
}
cout << endl;
for(auto num:radii)
{
cout << num << " ";
}
cout << endl;
*/
if(m==n-1)
{
return diameters[0];
}
if(m==n-2)
{
return max(radii[0]+radii[1]+l,diameters[0]);
}
else
{
return max(max(radii[0]+radii[1]+l,diameters[0]),radii[1]+radii[2]+2*l);
}
}
/*
int main()
{
int n,m,l,k;
cin >> n >> m >> l;
int a[n];
int b[n];
int t[n];
for(int i=0;i<n;i++)
{
cin >> k;
a[i] = k;
cin >> k;
b[i] = k;
cin >> k;
t[i] = k;
}
//cout << "owo" << endl;
cout << travelTime(n,m,l,a,b,t) << endl;
}
*/
