#include<bits/stdc++.h>
#define fi first
#define se second
#include "dreaming.h"
using namespace std;
vector<pair<int,int> > adj[1000000];
pair <int,int> par[100000];
int n,m,component, dis[100000],mx,start,end1,timer,tin[100000],tout[100000],ans ,comp[100000] , day;
int vis[100000];
void dfs (int v,int p,int val) {
if (dis[v] > mx) {
mx = dis[v];
start = v;
}
par[v] = {p,val};
for (auto i : adj[v]) {
if (i.fi != p) {
dis[i.fi] = dis[v] + i.se;
vis[i.fi] = vis[v];
dfs (i.fi, v, i.se);
}
}
}
void get_mid (int a,int b) {
// b is root
int distance = dis[a],down = 0;
ans = max (ans, distance);
comp[component] = distance;
int mn = INT_MAX;
while (a != b) {
down += par[a].se;
distance -= par[a].se;
mn = min (mn , max (down,distance));
a = par[a].fi;
}
if (mn == INT_MAX)
comp[component] = 0;
else comp[component] = mn;
}
int make_components() {
for (int i = 0; i < n; i++) {
if (!vis[i]) {
mx = INT_MIN;
component++;
vis[i] = (i ? vis[i-1] + 1 : 1);
dfs(i,-1,0);
end1 = start;
dis[start] = 0;
mx = INT_MIN;
dfs (end1,-1,0);
get_mid(start,end1);
}
}
int mn = comp[1],in = 1;
sort (comp + 1, comp + component + 1);
if (component == 1) return ans;
if (component == 2) {
return max (ans, comp[1] + comp[2] + day);
}
return max (ans, day*2 + comp[component - 1] + comp [component]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N; m = M; day = L;
for (int i = 0; i < m; i++) {
adj[A[i]].push_back( { B[i], T[i] });
adj[B[i]].push_back( { A[i], T[i] });
}
return make_components();
} /*
main () {
int N,M,L;
cin >> N >> M >> L;
int A[M],B[M],T[M];
for (int i = 0; i < M; i++)
cin >> A[i] >> B[i] >> T[i] ;
cout << travelTime(N, M, L, A, B, T);
} */
