#include "dreaming.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define INF 1005141919
#define _1 first
#define _2 second
int N, L;
vector<P> G[100000];
bool used[100000];
int dp1[100000], dp2[100000], src[100000];
inline void update(int x, int v, int s) {
if (v > dp1[x]) dp2[x] = dp1[x], dp1[x] = v, src[x] = s;
else if (v > dp2[x]) dp2[x] = v;
}
void dfs(int x, int p) {
used[x] = true;
dp1[x] = dp2[x] = 0;
src[x] = -1;
for (P pp : G[x]) if (pp._1 != p) {
int t = pp._1, len = pp._2;
dfs(t, x);
update(x, dp1[t]+len, t);
}
}
int diameter = 0;
int dfs2(int x, int p, int plen) {
if (p != -1) {
int v = dp1[p];
if (src[p] == x) v = dp2[p];
update(x, v+plen, p);
}
diameter = max(diameter, dp1[x]+dp2[x]);
int m = dp1[x];
for (P pp : G[x]) if (pp._1 != p) {
int t = pp._1, len = pp._2;
m = min(m, dfs2(t, x, len));
}
return m;
}
int travelTime(int N_, int M, int L_, int A[], int B[], int T[]) {
N = N_, L = L_;
rep(i, M) {
G[A[i]].pb(P(B[i], T[i]));
G[B[i]].pb(P(A[i], T[i]));
}
vector<int> X;
rep(i, N) if (!used[i]) {
dfs(i, -1);
X.pb(dfs2(i, -1, -1));
}
//cout<<"{";for(int x:X)cout<<x<<",";cout<<"}\n";
int m = diameter;
sort(all(X), greater<int>());
int cur_r = X[0];
for (int i=1; i<X.size(); i++) {
int r = X[i];
m = max(m, cur_r+r+L);
cur_r = min(max(cur_r, r+L), max(cur_r+L, r));
}
return m;
}
