#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int N, M, L, A[NMAX], B[NMAX], T[NMAX];
int v[NMAX], ix, mxd, r, ans;
vector<pair<int, int>> adj[NMAX], rt;
void dfs(int x, int p, int d){
v[x] = 1;
if(d > mxd) mxd = d, ix = x;
for(auto&[nx, t] : adj[x]){
if(nx == p) continue;
dfs(nx, x, d + t);
}
return;
}
int dfs2(int x, int p, int d){
if(d == mxd){
int mx = max(d, mxd - d);
if(mx < r) r = mx, ix = x;
return 1;
}
int ret = 0;
for(auto&[nx, t] : adj[x]){
if(nx == p) continue;
ret |= dfs2(nx, x, d + t);
}
if(ret) {
int mx = max(d, mxd - d);
if(mx < r) r = mx, ix = x;
}
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for(int i = 0; i < M; i++){
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
for(int i = 0; i < N; i++)
if(!v[i]) {
mxd = -1; dfs(i, -1, 0);
mxd = -1; dfs(ix, -1, 0);
r = mxd + 1;
ans = max(ans, mxd);
dfs2(ix, -1, 0);
rt.emplace_back(r, ix);
}
sort(all(rt)); reverse(all(rt));
if(rt.size() > 1) ans = max(ans, rt[0].first + rt[1].first + L);
if(rt.size() > 2) ans = max(ans, rt[1].first + rt[2].first + 2 * L);
return ans;
}
/*
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> L;
for(int i = 0; i < M; i++) cin >> A[i] >> B[i] >> T[i];
cout << travelTime(N, M, L, A, B, T);
return 0;
}*/
