#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10, INF=1e9+7;
vector<int>v[MAXN], w[MAXN], marc(MAXN, 0), d1(MAXN, 0), d2(MAXN, 0), d3(MAXN, 0), dt(MAXN, 0);
int radius, diameter, center;
void dfs(int x, int p){
marc[x]=1;
for(int k=0;k<v[x].size();k++){
if(v[x][k]!=p){
dfs(v[x][k], x);
if(d1[v[x][k]]+w[x][k]>d1[x]){
d2[x]=d1[x];
d1[x]=d1[v[x][k]]+w[x][k];
}else if(d1[v[x][k]]+w[x][k]>d2[x]){
d2[x]=d1[v[x][k]]+w[x][k];
}
}else{
swap(v[x][k], v[x][0]);
swap(w[x][k], w[x][0]);
}
}
}
void solve(int x, int p){
if(p!=-1){
if(d1[p]==d1[x]+w[x][0]){
d3[x]=max(d2[p], d3[p])+w[x][0];
}else{
d3[x]=max(d1[p], d3[p])+w[x][0];
}
}else if(v[x].size()!=0){
solve(v[x][0], x);
}
for(int k=1;k<v[x].size();k++){
solve(v[x][k], x);
}
int aux1=d1[x], aux2=d2[x], aux3=d3[x];
dt[x]=max({d1[x], d2[x], d3[x]});
if(dt[x]<radius){
center=x;
radius=dt[x];
diameter=max(d3[x], d2[x])+d1[x];
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]){
for(int k=0;k<m;k++){
v[a[k]].push_back(b[k]);
v[b[k]].push_back(a[k]);
w[a[k]].push_back(t[k]);
w[b[k]].push_back(t[k]);
}
int resp=0, r1=-1, r2=-1, r3=-1;
for(int k=0;k<n;k++){
if(marc[k]==0){
radius=INF;
diameter=INF;
dfs(k, -1);
solve(k, -1);
resp=max(resp, diameter);
if(r1<radius){
r3=r2;
r2=r1;
r1=radius;
}else if(r2<radius){
r3=r2;
r2=radius;
}else if(r3<radius){
r3=radius;
}
}
}
if(n-1>m){
resp=max(resp, r1+r2+l);
}
if(n-2>m){
resp=max(resp, r2+r3+2*l);
}
return resp;
}
/*int main(){
int n, m, l;
cin>>n>>m>>l;
int a[m], b[m], t[m];
for(int k=0;k<m;k++){
cin>>a[k]>>b[k]>>t[k];
}
cout<<travelTime(n, m, l, a, b, t);
}*/
