#include using namespace std; #define ALL(x) (x).begin(),(x).end() #define IO ios::sync_with_stdio(false),cin.tie(nullptr); #define LB(v, x) (ll)(lower_bound(ALL(v),x)-(v).begin()) #define UQ(v) sort(ALL(v)),(v).erase(unique(ALL(v)),v.end()) #define REP(i, n) for(ll i=0; i<(ll)(n); i++) #define FOR(i, a, b) for(ll i=(ll)(a); (a)<(b) ? i<(b) : i>(b); i+=((a)<(b) ? 1 : -1)) #define chmax(a, b) ((a)<(b) ? ((a)=(b), 1) : 0) #define chmin(a, b) ((a)>(b) ? ((a)=(b), 1) : 0) template using rpriority_queue=priority_queue,greater>; using ll=long long; const int INF=1e9+10; const ll INFL=4e18; using ld=long double; using ull=uint64_t; using VI=vector; using VVI=vector; using VL=vector; using VVL=vector; using PL=pair; using VP=vector; using WG=vector>>; // #include"kyopro_library/graph/shortest_path/dijkstra.hpp" /// @brief 重みなしグラフ g の頂点 start からの最短距離を求める /// @note O(E+V) VL BFS(const VVI& g, int start=0){ int n=g.size(); VL ret(n,INF); ret[start]=0; queue que; que.push(start); while(!que.empty()){ int now=que.front();que.pop(); for(int nxt:g[now])if(chmin(ret[nxt],ret[now]+1)) que.push(nxt); } return ret; } VL Dijkstra(const WG& g, int start=0){ int n=g.size(); VL ret(n,INFL); ret[start]=0; rpriority_queue> pq; pq.push({0,start}); VI seen(n); seen[start]=1; while(!pq.empty()){ auto [tmp,now]=pq.top();pq.pop(); if(ret[now]TreeDiameter(const WG& g){ VL dist=Dijkstra(g); int s=max_element(ALL(dist))-dist.begin(); dist=Dijkstra(g,s); int t=max_element(ALL(dist))-dist.begin(); VI path; int now=t; while(now!=s){ path.push_back(now); for(auto[nxt,cost]:g[now]){ if(dist[now]==dist[nxt]+cost){ now=nxt; break; } } } path.push_back(s); ll diameter=dist[t]; return {path,diameter}; } pairTreeDiameter(const vector& g){ VL dist=BFS(g); int s=max_element(ALL(dist))-dist.begin(); dist=BFS(g,s); int t=max_element(ALL(dist))-dist.begin(); VI path; int now=t; while(now!=s){ path.push_back(now); for(int nxt:g[now]){ if(dist[now]==dist[nxt]+1){ now=nxt; break; } } } path.push_back(s); ll diameter=dist[t]; return {path,diameter}; } int main(){ int N; cin>>N; WG G(N); REP(i,N-1){ ll u,v,w; cin>>u>>v>>w; u--,v--; G[u].push_back({v,w}); G[v].push_back({u,w}); } cout<