#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int nmax = 100000;
vector<array<int, 2>> graf[nmax];
int ans, cur;
int used[nmax], dist_down[nmax], dist_up[nmax];
void dfs_down(int v, int p = -1) {
used[v] = 1;
dist_down[v] = 0;
for(auto i : graf[v]) {
if(i[0] == p)
continue;
dfs_down(i[0], v);
dist_down[v] = max(dist_down[v], dist_down[i[0]] + i[1]);
}
return ;
}
void dfs_total(int v, int p = -1) {
array<int, 2> maximum[2];
maximum[0] = {-1, -1};
maximum[1] = {-1, -1};
for(auto i : graf[v]) {
if(i[0] == p)
continue;
int cur_dist = dist_down[i[0]] + i[1];
if(cur_dist > maximum[0][0]) {
maximum[0][0] = cur_dist;
maximum[0][1] = i[0];
}
else {
if(cur_dist > maximum[1][0]) {
maximum[1][0] = cur_dist;
maximum[1][1] = i[0];
}
}
}
cur = min(cur, max(dist_up[v], maximum[0][0]));
ans = max(ans, max(maximum[0][0], 0) + max(maximum[1][0], 0));
for(auto i : graf[v]) {
if(i[0] == p)
continue;
dist_up[i[0]] = dist_up[v] + i[1];
if(i[0] == maximum[0][1])
dist_up[i[0]] = max(dist_up[i[0]], maximum[1][0] + i[1]);
else
dist_up[i[0]] = max(dist_up[i[0]], maximum[0][0] + i[1]);
dfs_total(i[0], v);
}
return ;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
ans = 0;
for(int i = 0; i < m; i++) {
graf[a[i]].push_back({b[i], t[i]});
graf[b[i]].push_back({a[i], t[i]});
}
fill(used, used + n, 0);
fill(dist_down, dist_down + n, 0);
fill(dist_up, dist_up + n, 0);
vector<int> components;
for(int i = 0; i < n; i++) {
if(!used[i]) {
cur = 1000000010;
dfs_down(i);
dist_up[i] = 0;
dfs_total(i);
components.push_back(cur);
}
}
sort(components.begin(), components.end());
reverse(components.begin(), components.end());
if(components.size() > 1)
ans = max(ans, components[0] + l + components[1]);
if(components.size() > 2)
ans = max(ans, components[1] + l + l + components[2]);
return ans;
}
