#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <limits>
#include <tuple>
#include <stack>
#include <bitset>
#include <cstring>
#include <sstream>
#include <functional>
#include <random>
using namespace std;
#include "dreaming.in"
vector<vector<pair<int, int>>> adj;
vector<int> par;
vector<bool> vis;
void mark_cmp(int u) {
vis[u] = true;
for (auto& e : adj[u]) {
int v = e.first;
if (!vis[v]) {
mark_cmp(v);
}
}
}
void dfs(int u, int p, int d, pair<int, int>& mx) {
if (d > mx.second) {
mx = { u, d };
}
par[u] = p;
for (auto& e : adj[u]) {
int v = e.first, w = e.second;
if (v == p) {
continue;
}
dfs(v, u, d + w, mx);
}
}
int find_centar(int s) {
par.assign(adj.size(), -1);
pair<int, int> mx = { -1, -1 };
dfs(s, -1, 0, mx);
int B = mx.first;
par.assign(adj.size(), -1);
mx = { -1, -1 };
dfs(B, -1, 0, mx);
int C = mx.first;
int tot = mx.second;
vector<int> path;
for (int v = C; v != -1; v = par[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
vector<int> dist(path.size(), 0);
for (int i = 1; i < path.size(); ++i) {
int a = path[i - 1], b = path[i];
for (auto& e : adj[a]) {
if (e.first == b) {
dist[i] = dist[i - 1] + e.second;
break;
}
}
}
for (int i = 0; i < path.size(); ++i) {
if (dist[i] * 2 >= tot) {
return path[i];
}
}
return path.back();
}
int mx_dist(int s) {
par.assign(adj.size(), -1);
pair<int, int> mx = { -1, -1 };
dfs(s, -1, 0, mx);
return mx.second;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n, m, l;
n = N, m = M, l = L;
adj.assign(n, {});
for (int i = 0; i < m; ++i) {
int u, v, w;
u = A[i], v = B[i], w = T[i];
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
vis.assign(n, false);
par.assign(n, -1);
vector<int> c;
for (int u = 0; u < n; ++u) {
if (!vis[u]) {
mark_cmp(u);
c.push_back(mx_dist(find_centar(u)));
}
}
int ans = 0;
sort(c.rbegin(), c.rend());
if (c.size() == 1) {
ans = c[0];
}
else if (c.size() == 2) {
ans = c[0] + l + c[1];
}
else {
ans = max(c[1] + l + c[0], c[1] + 2 * l + c[2]);
}
return ans;
}
