#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 10;
vector<pair<int, int> > g[N];
bool vis[N];
int dist[N][2];
int idx, maxdist;
pair<int, int> diameter;
set<int> comp;
void Initialize() {
diameter.first = 0;
diameter.second = 0;
for(int i = 0; i < N; i++) {
g[i].clear();
vis[i] = false;
dist[i][0] = 0;
dist[i][1] = 0;
}
}
void dfs(int node, int par, int wt, int state) {
vis[node] = true;
comp.insert(node);
if(maxdist < wt) {
maxdist = wt;
idx = node;
}
dist[node][state] = wt;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i].first == par)
continue;
dfs(g[node][i].first, node, wt + g[node][i].second, state);
}
}
int travelTime(int n, int m, int l, int v[], int u[], int w[]) {
Initialize();
for(int i = 0; i < m; i++) {
g[u[i]].push_back({v[i], w[i]});
g[v[i]].push_back({u[i], w[i]});
}
int ans = 0;
vector<int> temp;
for(int i = 0; i < n; i++) {
if(!vis[i]) {
idx = 0;
maxdist = -1;
dfs(i, -1, 0, 0);
diameter.first = idx;
maxdist = -1;
dfs(idx, -1, 0, 0);
diameter.second = idx;
ans = max(ans, maxdist);
//cout << "i = " << i << ", diameter nodes = " << diameter.first << ", " << diameter.second << ", maxdist = " << maxdist << endl;
int best = maxdist;
maxdist = -1;
dfs(idx, -1, 0, 1);
for(auto i: comp) {
best = min(best, max(dist[i][0], dist[i][1]));
}
comp.clear();
temp.push_back(best);
}
}
sort(temp.begin(), temp.end());
reverse(temp.begin(), temp.end());
if(n - m >= 2) {
ans = max(ans, temp[0] + temp[1] + l);
}
if(n - m >= 3) {
ans = max(ans, temp[1] + temp[2] + 2 * l);
}
return ans;
}
/*int main() {
int n, m, l;
cin >> n >> m >> l;
int a[m], b[m], c[m];
for(int i = 0; i < m; i++) {
cin >> a[i] >> b[i] >> c[i];
}
cout << travelTime(n, m, l, a, b, c) << endl;
}*/
