#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
int ans=INT_MAX,sum;
int n1=0,n2=-1;
int solve(int now,int prev,vector<vector<pair<int,pair<int,int>>>> &path){
int rev=0;
for(int i=0;i<path[now].size();i++){
if(path[now][i].first==prev){
continue;
}
if(path[now][i].second.second==-1){
path[now][i].second.second=solve(path[now][i].first,now, path)+path[now][i].second.first;
}
rev=max(rev,path[now][i].second.second);
}
return rev;
}
// int ans=INT_MAX;
void solveeach(int now,vector<vector<pair<int,pair<int,int>>>> &path,vector<bool> &vst){
int cans=0;
vst[now]=1;
for(int i=0;i<path[now].size();i++){
if(!vst[path[now][i].first]){
solveeach(path[now][i].first,path,vst);
}
cans=max(path[now][i].second.second,cans);
}
ans=min(ans,cans);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
if(M==0){
return 2*L;
}
vector<vector<pair<int,pair<int,int>>>> path(N);
vector<bool> vst(N,false);
for(int i=0;i<M;i++){
path[A[i]].push_back({B[i],{T[i],-1}});
path[B[i]].push_back({A[i],{T[i],-1}});
}
// for(auto x:path){
// for(auto y:x){
// cout<<y.first<<','<<y.second.first<<','<<y.second.second<<' ';
// }
// cout<<'\n';
// }
// int n1=INT_MAX,n2_INT_MAX;
for(int j=0;j<N;j++){
for(int i=0;i<path[j].size();i++){
if(path[j][i].second.second==-1){
path[j][i].second.second=solve(path[j][i].first,j, path)+path[j][i].second.first;
}
ans=max(ans,path[j][i].second.second);
}
}
// for(auto x:path){
// for(auto y:x){
// cout<<y.first<<','<<y.second.first<<','<<y.second.second<<' ';
// }
// cout<<'\n';
// }
vector<int> ansk;
for(int i=0;i<N;i++){
ans=INT_MAX;
if(!vst[i]){
solveeach(i,path,vst);ansk.push_back(ans);
}
}
sort(ansk.begin(),ansk.end(),greater<int>());
// for(auto x:ansk){
// cout<<x<<' ';
// }
if(N==M-1) return ansk[0];
if(N-M>2)return max(ansk[0]+ansk[1]+L,ansk[1]+ansk[2]+2*L);
return ansk[0]+ansk[1]+L;
}
// #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("dreaming.in", "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);
// cin>>N>>M>>L;
// for(int i=0;i<M;i++){
// cin>>A[i]>>B[i]>>T[i];
// }
// int answer = travelTime(N, M, L, A, B, T);
// printf("%d\n", answer);
// return 0;
// }
