#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#include"dreaming.h"
ll ans = 0, fnode = 0;
vector<vector<pll>> adj;
vector<bool> vis;
vector<ll> sz, parent;
ll find(ll x){
if (parent[x] != x){return parent[x] = find(parent[x]);}
else return x;
}
void make(ll a, ll b, ll val){
a = find(a);
b = find(b);
if (sz[a] < sz[b]) swap(a,b);
parent[b] = a;
sz[a] = val + sz[b];
}
void dfs(ll node, ll par, ll width){
for (auto [neigh, val] : adj[node]){
if (neigh == par) continue;
dfs(neigh, node, width + val);
}
if (ans < width){
fnode = node;
ans = width;
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
//vis.resize(N,false);
adj.resize(N);
sz.resize(N,0);
parent.resize(N);
vector<ll> indeg(N,0);
for(ll i =0 ; i<N;i++){parent[i] = i;}
for (ll i = 0 ; i < M; i++){
adj[A[i]].push_back({B[i], T[i]});
indeg[A[i]] ++;
indeg[B[i]] ++;
adj[B[i]].push_back({A[i], T[i]});
}
deque<ll> q;
for (ll i = 0 ; i < N; i++){
if (indeg[i] == 1){q.push_back(i);}
}
while (!q.empty()){
ll node = q.front();
q.pop_front();
for (auto [neigh, val] : adj[node]){
make(neigh, node, val);
indeg[neigh] --;
if (indeg[neigh] == 1) q.push_back(neigh);
}
}
for (ll i = 1; i < N; i++){
if (find(i) != find(0)){
//cout << "Add: " << parent[i] << " " << parent[0] << " " << L << endl;
adj[parent[i]].push_back({parent[0], L});
adj[parent[0]].push_back({parent[i],L});
make(parent[0], parent[i] , L);
}
}
// for (ll i =0 ; i < N; i++){
// cout << i << " " << (find(i) == i ? -1 : find(i)) << endl;
// }
dfs(parent[0], -1, 0);
dfs(fnode, -1, 0);
return ans;
}
// int main(){
// int A[] ={0,8,2,5,5,1,1,10};
// int B[] ={8,2,7,11,1,3,9,6};
// int T[] = {4,2,4,3,7,1,5,3};
// ll N = 12;
// ll M = 8;
// ll L = 2;
// cout << travelTime(N, M, L, A, B, T);
// }
