#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
vector<vector<pii>> graph;
vector<int> was;
pii find(int v, int pr = -1)
{
was[v] = 1;
pii cur = {0, v};
for (auto tov : graph[v])
if (tov.f != pr)
{
pii to = find(tov.f, v);
to.f += tov.s;
cur = max(cur, to);
}
return cur;
}
pii solve(int v, int dpth, int pr = -1)
{
int cur = 0;
int res = dpth;
for (auto tov : graph[v])
if (tov.f != pr)
{
pii to = solve(tov.f, dpth + tov.s, v);
if (to.f + tov.s > cur)
{
cur = to.f + tov.s;
res = min(to.s, max(dpth, cur));
}
}
return {cur, res};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
graph.resize(N);
was.resize(N);
for (int i = 0; i < M; ++i)
{
graph[A[i]].pb({B[i], T[i]});
graph[B[i]].pb({A[i], T[i]});
}
vector<int> d;
int res = 0;
for (int i = 0; i < N; ++i)
if (!was[i])
{
int D1 = find(i).s;
pii cur = solve(D1, 0);
res = max(res, cur.f);
d.pb(cur.s);
// cout << i << " " << D1 << ": " << res.f << " " << res.s << "\n";
}
sort(all(d));
reverse(all(d));
if (d.size() > 1)
res = max(res, d[0] + L + d[1]);
if (d.size() > 2)
res = max(res, d[1] + L + d[2] + L);
return res;
}
// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include "dreaming.h"
// #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;
// assert(scanf("%d%d%d", &N, &M, &L) == 3);
// for (i = 0; i < M; i++)
// assert(scanf("%d%d%d", &A[i], &B[i], &T[i]) == 3);
// int answer = travelTime(N, M, L, A, B, T);
// printf("%d\n", answer);
// return 0;
// }
// WAT
