#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
struct yal{
int u,v,w;
int getad(int fu){
return (u^v^fu);
}
}alle[maxn];
int n,m,l,mainres=0,vis[maxn];
vector<int>adj[maxn];
pair<int,int>mx[maxn];
pair<int,int>comp(pair<int,int>a,int b){
if(b>a.first){
a.first=b;
if(a.first>a.second){
swap(a.first,a.second);
}
}
return a;
}
void dfsdown(int u,int par=-1){
mx[u]=make_pair(0,0);
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v==par){
continue;
}
dfsdown(v,u);
mx[u]=comp(mx[u],mx[v].second+alle[x].w);
}
return ;
}
void dfsup(int u,int par=-1,int l=0){
mx[u]=comp(mx[u],l);
mainres=max(mainres,mx[u].first+mx[u].second);
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v==par){
continue;
}
int z=mx[u].second;
if(mx[u].second==mx[v].second+alle[x].w){
z=mx[u].first;
}
dfsup(v,u,z+alle[x].w);
}
}
int get(int u,int par=-1){
int ret=u;
vis[u]=1;
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v==par){
continue;
}
int r=get(v,u);
if(mx[ret].second>mx[r].second){
ret=r;
}
}
return ret;
}
int calc(int u){
dfsdown(u);
dfsup(u);
return mx[get(u)].second;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N;
m=M;
l=L;
for(int i=0;i<m;i++){
alle[i].u=A[i];
alle[i].v=B[i];
alle[i].w=T[i];
adj[alle[i].u].push_back(i);
adj[alle[i].v].push_back(i);
}
vector<int>alls;
for(int i=0;i<n;i++){
if(vis[i]==0){
alls.push_back(calc(i));
// cout<<alls.back()<<endl;
}
}
sort(alls.rbegin(),alls.rend());
if((int)alls.size()==2){
mainres=max(mainres,alls[0]+alls[1]+l);
}
if((int)alls.size()>=3){
mainres=max(mainres,alls[0]+alls[1]+l);
mainres=max(mainres,alls[1]+alls[2]+2*l);
}
return mainres;
}
