#include <bits/stdc++.h>
#include "dreaming.h"
#define f first
#define s second
using namespace std;
const int maxn = 1e5 + 69;
vector<pair<int, int>> g[maxn];
vector<int> vis(maxn);
vector<int> d(maxn), par(maxn);
vector<int> t;
void dfs(int v, int p) {
vis[v] = true;
t.push_back(v);
par[v] = p;
for(auto u : g[v]) {
if(u.f != p) {
d[u.f] = d[v] + u.s;
dfs(u.f, v);
}
}
}
int find_minmax(vector<int> &v, int dija) {
//v->cvorovi koji cine dijametar stabla
int mn = 1e9, res = -1;
for(auto x : v) {
int y = max(d[x], dija - d[x]);
if(mn >= y) {
mn = y;
res = x;
}
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0;i < M;i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<int> r;
for(int i = 0;i < N - 1;i++) {
if(!vis[i]) {
t.clear();
dfs(i, -1);
int s, mx = 0;
for(auto x : t) {
if(d[x] >= mx) {
mx = d[x];
s = x;
}
}
t.clear();
d[s] = 0;
dfs(s, -1);
mx = 0;
for(auto x : t) {
if(d[x] >= mx) {
mx = d[x];
s = x;
}
}
vector<int> c;
while(s != -1) {
c.push_back(s);
s = par[s];
}
r.push_back(find_minmax(c, mx));
}
}
for(int i = 1;i < (int)r.size();i++) {
g[r[i]].push_back({r[i - 1], L});
g[r[i - 1]].push_back({r[i], L});
}
dfs(0, -1);
int s, mx = 0;
for(auto x : t) {
if(d[x] >= mx) {
mx = d[x];
s = x;
}
}
t.clear();
d[s] = 0;
dfs(s, -1);
int ans = 0;
for(int i = 0;i < N - 1;i++)
ans = max(ans, d[i]);
return ans;
}
//
// int main()
// {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// int tt = 1;
// //cin >> tt;
// while(tt--) {
// int n, m, l;
// cin >> n >> m >> l;
// int a[m], b[m], t[m];
// for(int i = 0;i < m;i++)
// cin >> a[i] >> b[i] >> t[i];
// cout << travelTime(n, m, l, a, b, t);
// }
// return 0;
// }
