#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int N, M, L;
bool vis[100001];
vector <pair <int, int> > v[100001];
vector <int> path;
map <pair <int, int>, int> cost;
void dfs(int node, int pnode, int dep, pair <int, int> &ret){
vis[node] = 1;
if(dep > ret.second)
ret = make_pair(node, dep);
for(auto &i : v[node])
if(i.first != pnode)
dfs(i.first, node, dep + i.second, ret);
}
bool find(int node, int pnode, int target){
if(node == target) return 1;
for(auto &i : v[node]){
if(i.first == pnode) continue;
if(find(i.first, node, target) == 0) continue;
path.push_back(i.first);
return 1;
}
return 0;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
N = n;
M = m;
L = l;
for(int i = 0 ; i < M ; i++){
v[A[i]].push_back(make_pair(B[i], T[i]));
v[B[i]].push_back(make_pair(A[i], T[i]));
cost[make_pair(A[i], B[i])] = cost[make_pair(B[i], A[i])] = T[i];
}
int ans = 0;
vector <int> a;
for(int i = 0 ; i < N ; i++){
if(vis[i]) continue;
pair <int, int> f = make_pair(-1, -1);
dfs(i, -1, 0, f);
pair <int, int> s = make_pair(-1, -1);
dfs(f.first, -1, 0, s);
ans = max(ans, s.second);
path.clear();
find(f.first, -1, s.first);
path.push_back(f.first);
int c = s.second;
int cur = s.second;
for(int j = 1 ; j < path.size() ; j++){
cur -= cost[make_pair(path[j], path[j - 1])];
c = min(c, max(cur, s.second - cur));
}
a.push_back(c);
}
sort(a.rbegin(), a.rend());
if(a.size() > 1)
ans = max(ans, a[0] + a[1] + L);
if(a.size() > 2)
ans = max(ans, a[1] + a[2] + 2 * L);
return ans;
}
