#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
using pii = pair<ll, ll>;
vector<vector<pair<ll,ll>>> neighbours(n,vector<pair<ll,ll>>());
ll w,x,y,z;
for(int i=0;i<m;i++)
{
x=a[i];
y=b[i];
z=t[i];
neighbours[x].push_back(make_pair(y,z));
neighbours[y].push_back(make_pair(x,z));
}
vector<bool> seen(n,false);
vector<bool> currseen(n,false);
vector<ll> temparr;
vector<ll> path(n,-1);
vector<ll> firstpassweight(n,-1);
vector<ll> weight(n,-1);
ll neighbour,edgeweight;
ll d,r1,r2,r3;
d=0;r1=0;r2=0;r3=0;
for(int i=0;i<n;i++)
{
if(!seen[i])
{
stack<ll> q({i});
ll ep1,ep2,curr,total,currfurthest,currfurthestdistance;
firstpassweight[i]=0;
currfurthestdistance=-1;
ep1=i;
while(!q.empty())
{
curr = q.top();
q.pop();
seen[curr]=true;
for(auto &pa:neighbours[curr])
{
neighbour=pa.first;
edgeweight=pa.second;
if(!seen[neighbour])
{
firstpassweight[neighbour]=firstpassweight[curr]+edgeweight;
if(firstpassweight[neighbour]>currfurthestdistance)
{
currfurthestdistance=firstpassweight[neighbour];
ep1=neighbour;
}
q.push(neighbour);
}
}
}
ep2=ep1;
currfurthestdistance=-1;
total=0;
weight[ep1]=0;
stack<ll>({ep1}).swap(q);
while(!q.empty())
{
curr = q.top();
q.pop();
currseen[curr]=true;
for(auto &pa:neighbours[curr])
{
neighbour=pa.first;
edgeweight=pa.second;
if(!currseen[neighbour])
{
path[neighbour]=curr;
weight[neighbour]=weight[curr]+edgeweight;
if(weight[neighbour]>currfurthestdistance)
{
currfurthestdistance=weight[neighbour];
ep2=neighbour;
}
q.push(neighbour);
}
}
}
ll 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];
}
vector<ll>({r1,r2,r3,x}).swap(temparr);
sort(temparr.begin(),temparr.end());
r1=temparr[3];
r2=temparr[2];
r3=temparr[1];
d=max(d,weight[ep2]);
}
}
if(m==n-1)
{
return d;
}
if(m==n-2)
{
return max(d,r1+r2+l);
}
else
{
return max(max(d,r1+r2+l),r2+r3+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;
}
*/
