#include <stdio.h>
#include <stdlib.h>
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> grafo[100005],peso[100005],v,dist;
int part,best,tmp,ans,sum;
bool vis[100005];
void dfs1(int nodo,int val,int last){
//cout<<nodo<<" "<<val<<endl;
if(val>best){
best=val;
part=nodo;
}
for(int i=0;i<grafo[nodo].size();i++){
if(grafo[nodo][i]!=last){
dfs1(grafo[nodo][i],val+peso[nodo][i],nodo);
}
}
}
bool dfs2(int nodo,int last){
if(nodo==part)return true;
for(int i=0;i<grafo[nodo].size();i++){
if(grafo[nodo][i]!=last){
if(dfs2(grafo[nodo][i],nodo)==true){
v.push_back(peso[nodo][i]);
return true;
}
}
}
return false;
}
void dfs(int nodo){
vis[nodo]=true;
for(int i=0;i<grafo[nodo].size();i++){
if(vis[grafo[nodo][i]]==false)
dfs(grafo[nodo][i]);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++){
grafo[A[i]].push_back(B[i]);
grafo[B[i]].push_back(A[i]);
peso[A[i]].push_back(T[i]);
peso[B[i]].push_back(T[i]);
}
for(int i=0;i<N;i++){
if(vis[i]==false){
best=0;
part=i;
dfs1(i,0,-1);
best=0;
tmp=part;
dfs1(part,0,-1);
v.clear();
dfs2(tmp,-1);
dfs(i);
ans=max(ans,best);
sum=0;
int tmp2=best;
for(int j=0;j<v.size();j++){
sum+=v[j];
tmp2=min(tmp2,max(sum,best-sum));
}
dist.push_back(tmp2);
//cout<<best<<" edasd "<<tmp2<<endl;
}
}
sort(dist.begin(),dist.end());
if(dist.size()>=2)
ans=max(ans,dist[dist.size()-1]+dist[dist.size()-2]+L);
if(dist.size()>=3)
ans=max(ans,dist[dist.size()-3]+dist[dist.size()-2]+2*L);
return ans;
}
/*
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
int N, M, L, i;
int res;
FILE *f = fopen("input.txt", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
fclose(f);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}*/
