#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define mp make_pair
const int N = 1e5+7, INF = 0x3f3f3f3f;
int comp, tmpfurthdis, tmpfurth;
vector <int> compnum(N), compfurthdis(N, INF), compfurth(N), vis(N), disfromeach(N);
vector <pii> compends(N);
vector <vector <pii>> graph(N);
vector <vector <int>> compelem(N);
void findcomp(int v, int num){
vis[v] = 1;
compnum[v] = num;
compelem[num].pb(v);
for(auto to : graph[v]){
if(!vis[to.first]){
findcomp(to.first, num);
}
}
}
void findends(int v, int p = -1, int dis = 0){
if(dis > tmpfurthdis){
tmpfurthdis = dis;
tmpfurth = v;
}
for(auto to : graph[v]){
if(to.first != p){
findends(to.first, v, dis+to.second);
}
}
}
void finddis(int v, int p = -1, int dis = 0){
disfromeach[v] = max(disfromeach[v], dis);
for(auto to : graph[v]){
if(to.first != p){
finddis(to.first, v, dis+to.second);
}
}
}
int travelTime(int n, int m, int l, int x[], int y[], int t[]) {
int i, ans = 0;
for(i = 0; i < m; i++){
graph[x[i]].pb(mp(y[i], t[i]));
graph[y[i]].pb(mp(x[i], t[i]));
}
for(i = 0; i < n; i++){
if(!vis[i]){
findcomp(i, comp++);
}
}
for(i = 0; i < n; i++)
vis[i] = 0;
for(i = 0; i < comp; i++){
int to = compelem[i][0];
tmpfurthdis = 0;
tmpfurth = to;
findends(to);
compends[i].first = tmpfurth;
tmpfurthdis = 0;
findends(tmpfurth);
compends[i].second = tmpfurth;
ans = max(ans, tmpfurthdis);
}
for(i = 0; i < comp; i++){
finddis(compends[i].first);
finddis(compends[i].second);
}
for(i = 0; i < n; i++){
if(compfurthdis[compnum[i]] > disfromeach[i]){
compfurthdis[compnum[i]] = disfromeach[i];
compfurth[compnum[i]] = i;
}
}
vector <int> dists;
for(i = 0; i < comp; i++){
dists.pb(compfurthdis[i]);
}
sort(dists.rbegin(), dists.rend());
if(comp > 1){
ans = max(ans, dists[0]+l+dists[1]);
}
if(comp > 2){
ans = max(ans, dists[1]+l+l+dists[2]);
}
/*
for(i = 0; i < n; i++){
cout << compnum[i] << ' ';
}
cout << endl;
for(i = 0; i < comp; i++){
cout << compends[i].first << ' ' << compends[i].second << endl;
}*/
return ans;
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
/*
int main(){
int n, m, i, l;
cin >> n >> m >> l;
int x[m], y[m], t[m];
for(i = 0; i < m; i++){
cin >> x[i] >> y[i] >> t[i];
}
cout << travelTime(n, m, l, x, y, t);
}*/
