#include "dreaming.h"
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
///#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
const ll inf = 2e9;
const int maxn = 1e5+10;
const int mod = 1e9+7;
vector<pii> g[maxn];
bool mark[maxn];
vector<int> fel;
int par[maxn], V;
int down[maxn], up[maxn], ANS = 0;
void dfs(int v)
{
mark[v] = 1;
int MX = 0;
for(auto e : g[v])
{
int u = e.F, w = e.S;
if(u != par[v])
{
par[u] = v;
dfs(u);
down[v] = max(down[u]+w, down[v]);
up[u] = max(up[u], MX + w);
MX = max(MX, down[u]+w);
}
}
MX = 0;
reverse(g[v].begin(), g[v].end());
for(auto e : g[v])
{
int u = e.F, w = e.S;
if(u != par[v])
{
up[u] = max(up[u], MX + w);
MX = max(MX, down[u]+w);
}
}
reverse(g[v].begin(), g[v].end());
}
int MN = inf;
void lfs(int v)
{
for(auto e : g[v])
{
int u = e.F, w = e.S;
if(u != par[v])
{
up[u] = max(up[u], up[v] + w);
lfs(u);
}
}
//cout<< v <<" "<< down[v] <<" "<< up[v] <<"\n";
int door = max(up[v], down[v]);
ANS = max(ANS,door);
MN = min(MN, door);
}
/*int A[8] = {0, 8, 2, 5, 5, 1, 1, 10};
int B[8] = {8, 2, 7, 11, 1, 3, 9, 6};
int T[8] = {4, 2, 4, 3, 7, 1, 5, 3};*/
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for(int i = 0; i < M; i++)
{
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
for(int v = 0; v < N; v++)
if(!mark[v])
{
MN = inf;
dfs(v); lfs(v);
fel.push_back(MN);
//cout<< MN <<" ";
}
sort(fel.begin(), fel.end());
if((int)fel.size() == 1) return ANS;
if((int)fel.size() == 2) return max(fel[0] + fel[1] + L, ANS);
//cout<< ANS <<" ";
int MM = (int)fel.size();
return max({fel[MM-1] + fel[MM-2] + L, fel[MM-2] + fel[MM-3] + 2 * L, ANS});
}/*
signed main()
{
//ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout<< travelTime(12, 8, 2);
}
*/
