#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int N, M, L;
vector <int> DP[2];
vector <pair <int, int>> VG[100001];
inline pair <int, int> DFS(int node, int parent = 0)
{
pair <int, int> ret = {DP[0][node], node};
for(pair <int, int> p : VG[node])
{
if(p.second == parent) continue;
DP[0][p.second] = DP[0][node] + p.first;
ret = max(DFS(p.second, node), ret);
}
return ret;
}
inline int MDFS(int node, int parent = 0)
{
int ret = max(DP[0][node], DP[1][node]);
for(pair <int, int> p : VG[node]) if(p.second != parent) ret = min(MDFS(p.second, node), ret);
return ret;
}
inline pair <int, int> Diameter(int node)
{
int u = DFS(node).second;
DP[0][u] = 0;
int v = DFS(u).second;
swap(DP[0], DP[1]);
int diameter = DFS(v).first;
int minimum = MDFS(v);
return {diameter, minimum};
}
int travelTime(int n, int m, int l, int u[], int v[], int w[])
{
N = n;
DP[0].resize(N + 1);
DP[1].resize(N + 1);
M = m;
L = l;
for(int i = 0; i < M; i++)
{
VG[u[i] + 1].push_back({w[i], v[i] + 1});
VG[v[i] + 1].push_back({w[i], u[i] + 1});
}
int diameter = 0, maximum[3];
maximum[0] = maximum[1] = maximum[2] = 0;
for(int i = 1; i <= N; i++)
{
if(DP[0][i] || DP[1][i] || !VG[i].size()) continue;
// cout << i << ":\n";
pair <int, int> temp = Diameter(i);
if(!temp.first) continue;
// cout << temp.first << ' ' << temp.second << '\n';
diameter = max(temp.first, diameter);
for(int j = 0; j < 3; j++)
{
if(temp.second <= maximum[j]) continue;
for(int k = 2; k > j; k--) maximum[k] = maximum[k - 1];
maximum[j] = temp.second;
break;
}
}
// cout << "maximum:\n";
// for(int j = 0; j < 3; j++) cout << maximum[j] << " \n"[j == 2];
if(M == (N - 1)) return diameter;
if(M == (N - 2)) return max(diameter, maximum[0] + maximum[1] + L);
return max({diameter, maximum[0] + maximum[1] + L, maximum[1] + maximum[2] + L + L});
}
//int main()
//{
// int n, m, l, u[100], v[100], w[100];
// cin >> n >> m >> l;
// for(int i = 0; i < m; i++) cin >> u[i] >> v[i] >> w[i];
// cout << travelTime(n, m, l, u, v, w) << '\n';
//
// return 0;
//}
