/* input
*/
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
vector<pair<int, int>> adj[N];
vector<int> nodes;
int it, up[N], down[N][2], radius[N]; bool dd[N];
void calc_down(int x, int par) {
nodes.push_back(x); dd[x] = 1;
for (pair<int, int> v : adj[x]) if (v.first != par) {
int i, w; tie(i, w) = v;
calc_down(i, x);
if (down[i][0] + w > down[x][0]) {
down[x][1] = down[x][0];
down[x][0] = down[i][0] + w;
}
else if (down[i][0] + w > down[x][1]) down[x][1] = down[i][0] + w;
}
}
void calc_up(int x, int par) {
for (pair<int, int> v : adj[x]) if (v.first != par) {
int i, w; tie(i, w) = v;
up[i] = up[x] + w;
if (down[i][0] + w == down[x][0]) up[i] = max(up[i], down[x][1] + w);
else up[i] = max(up[i], down[x][0] + w);
calc_up(i, x);
}
}
int travelTime(int n, int m, int l, int x[], int y[], int w[]) {
for (int i = 0; i < m; ++i) {
++x[i]; ++y[i];
adj[x[i]].push_back(make_pair(y[i], w[i]));
adj[y[i]].push_back(make_pair(x[i], w[i]));
}
int res = 0;
for (int i = 1; i <= n; ++i) if (!dd[i]) {
++it; nodes.clear();
calc_down(i, 0);
calc_up(i, 0);
radius[it] = 2e9;
for (int t : nodes) {
radius[it] = min(radius[it], max(up[t], down[t][0]));
res = max(res, up[t] + down[t][0]);
}
}
sort(radius + 1, radius + it + 1, greater<int>());
if (it > 1) res = max(res, radius[1] + radius[2] + l);
if (it > 2) res = max(res, radius[2] + radius[3] + 2 * l);
return res;
}
