#include "dreaming.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
vector< pair<int, int> > v[100005];
int bio[100005];
int prt[100005];
int g[100005];
int da[100005];
vector<int> sol;
vector<int> dj;
int rek(int x, int p) {
da[x] = 1;
int rj = max(bio[x], g[x]);
for (int i = 0; i < (int)v[x].size(); i++) {
if (v[x][i].X != p) {
rj = min(rj, rek(v[x][i].X, x));
}
}
return rj;
}
int dfs(int x, int p) {
bio[x] = 0;
prt[x] = p;
for (int i = 0; i < (int)v[x].size(); i++) {
if (v[x][i].X != p) bio[x] = max(bio[x], dfs(v[x][i].X, x)+v[x][i].Y);
}
return bio[x];
}
void dfs2(int x, int p) {
vector<int> tren;
for (int i = 0; i < (int)v[x].size(); i++) {
if (v[x][i].X != p) tren.push_back(bio[v[x][i].X]+v[x][i].Y);
}
sort(tren.begin(), tren.end());
int post = 1;
if (p == -1) post = 0;
if ((int)tren.size() >= 2) {
for (int i = 0; i < (int)v[x].size(); i++) {
if (v[x][i].X != p) {
int pos =(int)tren.size()-1;
if (tren[pos] == bio[v[x][i].X]+v[x][i].Y) pos--;
g[v[x][i].X] = max(tren[pos]+v[x][i].Y, g[x]+v[x][i].Y);
}
}
}
else if ((int)tren.size() == 1) {
if (v[x][0].X != p) g[v[x][0].X] = g[x]+v[x][0].Y;
else g[v[x][1].X] = g[x]+v[x][1].Y;
}
for (int i = 0; i < (int)v[x].size(); i++) {
if (v[x][i].X != p) dfs2(v[x][i].X, x);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int c[]) {
for (int i = 0; i < m; i++) {
v[a[i]].push_back({b[i], c[i]});
v[b[i]].push_back({a[i], c[i]});
}
memset(bio, -1, sizeof bio);
for (int i = 0; i < n; i++) {
if (bio[i] == -1) {
dfs(i, -1);
dfs2(i, -1);
}
}
for (int i = 0; i < n; i++) {
if (da[i] == 0) sol.push_back(rek(i, -1));
}
int out = 0;
sort(sol.begin(), sol.end());
if (sol.size() >= 2) out = max(out, sol.back()+l+sol[(int)sol.size()-2]);
if (sol.size() >= 3) out = max(out, sol[(int)sol.size()-2]+2*l+sol[(int)sol.size()-3]);
for (int i = 0; i < n; i++) {
dj.clear();
for (int j = 0; j < (int)v[i].size(); j++) {
if (v[i][j].X != prt[i]) dj.push_back(bio[v[i][j].X]+v[i][j].Y);
}
sort(dj.begin(), dj.end());
reverse(dj.begin(), dj.end());
if ((int)dj.size() >= 2) out = max(out, dj[0]+dj[1]);
if (prt[i] != -1) out = max(out, bio[i]+g[i]);
}
return out;
}
