// Jesu juva
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vull vector<ull>
#define vb vector<bool>
#define vpii vector<pii>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvpii vector<vpii>
#define f(i,x,n) for(int i=x;i<n;i++)
#define fe(i,x,n) for(int i=x;i<=n;i++)
vb vis(1e6 + 5, false);
vi parent(1e6 + 5);
vi dist(1e6 + 5, INT_MAX);
vvpii adj(1e6 + 5,vpii());
int dep1,dep2;
void dfs(int root, bool mark) {
vis[root] = mark;
//* cout << "NODE " << root << " DIST " << dist[root] << endl;
if (adj[root].size() == 1) {
if (vis[adj[root][0].first]) {
//* cout << "TRIGGA1" << endl;
if (dist[root] > dist[dep2]) dep2 = root;
return;
}
else if (dist[adj[root][0].first] != INT_MAX && !mark){
//* cout << "TRIGGATOO" << endl;
if (dist[root] > dist[dep1]) dep1 = root;
return;
}
}
for (auto &edge : adj[root]) {
if ((dist[edge.first] != INT_MAX && !mark) || vis[edge.first]) continue;
dist[edge.first] = dist[root] + edge.second;
if (mark) parent[edge.first] = root;
dfs(edge.first, mark);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int d1=0,r1=0,r2=0,r3=0;
f(i,0,M) {
adj[A[i]].emplace_back(B[i],T[i]);
adj[B[i]].emplace_back(A[i],T[i]);
}
/*f(i,0,N) {
cout << "NODE " << i << endl;
for (auto x: adj[i]) {
cout << x.first << ' ' << x.second << endl;
}
cout << endl;
}*/
f(i,0,M) {
if (vis[i]) continue;
// found a new CC ITS A BLOODY TREEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE
// AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
// find diameter endpoint 1
dist[i] = 0;
dep1 = i;
//* cout << endl;
dfs(i,false);
//* cout << "DEP1 " << dep1 << endl << endl;
// find diameter endpoint 2
parent[dep1] = -1;
dep2 = dep1;
dist[dep1] = 0;
dfs(dep1,true);
//* cout << "DEP2 " << dep2 << endl << endl;
// check if diameter is the largest
d1 = max(dist[dep2],d1);
//* cout << "DIAMITTAH " << dist[dep2] << endl <<endl;
// cut if only 1 connected component exists
if (N-M==1) return d1;
// go along diameter until we find the node that minimizes its distance with the farther diameter endpoint
int radius = INT_MAX;
{
int u = dep2;
while(u!=-1) {
// bottom side dist[u]
// top side dist[dep2] - dist[u]
radius = min(radius, max(dist[u], dist[dep2] - dist[u]));
u = parent[u];
}
}
//* cout << "RADIUS " << radius << endl << endl;
// check if radius is in the top 3
if (radius > r1) {
r3 = r2;
r2 = r1;
r1 = radius;
}
else if (radius > r2) {
r3 = r2;
r2 = radius;
}
else if (radius > r3) {
r3 = radius;
}
// else useless cc
}
//* cout << "ANS " << d1 << ' ' << r1 << ' ' << r2 << ' ' << r3<< ' ' << L << endl;
if (N-M==2) {
return max(d1, r1+r2+L);
}
else {
return max(d1, max(r1+L+r2, r2+L+L+r3));
}
}
/*
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m,l;
cin >> n >> m >> l;
int a[n],b[n],t[n];
f(i,0,m) {
cin >> a[i] >> b[i] >> t[i];
}
cout << travelTime(n,m,l,a,b,t) << endl;
}*/
// soli Deo gloria
