#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef map<ll, ll> mp;
typedef pair<ll, ll> pll;
typedef queue<ll> qi;
typedef vector<ll> vi;
typedef vector <vi> vvi;
typedef vector <pll> vpl;
typedef vector <string> vs;
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define F first
#define S second
#define pb push_back
#define all(x) begin(x), end(x)
#define MAXN 100001
ll br=0, t=1, sl=-1;
vector<pll> adj[MAXN];
ll comp[MAXN],dist[MAXN];
ll tin[MAXN], to[MAXN],fenw[MAXN+1];
vi nds[MAXN];
vi answ;
void dfs(ll nd, ll pr){
comp[nd]=br;
nds[br].pb(nd);
for (pll par: adj[nd]){
ll s=par.F, w=par.S;
if(s==pr) continue;
dist[s]=dist[nd]+w;
dfs(sl, nd);
}
}
void dfs1(ll nd, ll pr) {
tin[nd]=t;
t++;
for (pll par: adj[nd]) {
ll s=par.F, w=par.S;
if (s == pr) continue;
dist[s] = dist[nd] + w;
dfs1(s, nd);
}
to[nd]=t-1;
}
void update(ll pos, ll val) {
for (ll i=pos; i <=t + 1; i+=i&(-i)) fenw[i] += val;
}
ll query(ll pos) {
ll sum=0;
for (ll i=pos; i>0; i-=i&(-i)) sum+=fenw[i];
return sum;
}
void resi(ll comp, ll n) {
ll maxdist=0, maxnode=nds[comp][0];
for (ll node: nds[comp]) {
if (dist[node] > maxdist) {
maxdist=dist[node];
maxnode=node;
}
}
t=1; dist[maxnode]=0; dfs1(maxnode, 0);
ll len=0, sol=len;
for (ll i=1; i<=t+1; i++) fenw[i]=0;
for (ll node: nds[comp]) {
len=max(len, dist[node]);
sol=len;
}
for (ll node: nds[comp]) {
if (dist[node] == len) update(tin[node], 1);
}
for (ll node: nds[comp]) {
ll value=max(dist[node], len-dist[node]);
if (value >= sol) continue;
if (value == dist[node]) {
sol=min(sol, value);
continue;
}
ll broj=query(to[node]) - query(tin[node]-1);
if (broj > 0) sol=min(sol, value);
}
answ.pb(sol);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for (int i=0; i<m; i++) {
int node1=a[i]+1, node2=b[i]+1, wp=t[i];
adj[node1].pb({node2, wp});
adj[node2].pb({node1, wp});
}
for(int node=1; node<=n; node++) {
if (comp[node] == 0) {
br++;
dfs(node, 0);
}
}
for (int komp=1; komp<=br; komp++) resi(komp, n);
sort(answ.begin(), answ.end());
int ans=0, slucaj=0;
return ans;
}
