#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //using namespace atcoder; using namespace std; #define P pair #define Graph vector> #define float long double #define rep(i,a,b) for(int i=(a);i<(b);++i) #define repi(itr,m) for(auto itr=(m).begin();itr!=(m).end();itr++) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define vi vector #define int long long const int INF=1e18; int dx[8]={0,1,0,-1,-1,-1,1,1}; int dy[8]={1,0,-1,0,-1,1,-1,1}; #include template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false));} template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false));} struct point{ int x,y; }; void yn(bool t){ if(t)cout<<"Yes"<>n; vector>g(n+1); rep(i,1,n){ int u,v,w;cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); } vectordist1(n+1,-INF); dist1[3]=0; queue

pq;//to come pq.push({3,0}); while(!pq.empty()){ auto [to,come]=pq.front(); pq.pop(); for(auto [v,cost]:g[to]){ if(v==come)continue; dist1[v]=dist1[to]+cost; pq.push({v,to}); } } priority_queue

cnt; rep(i,1,n+1)cnt.push({dist1[i],i}); int ans=-INF; while(1){ auto [cost,idx]=cnt.top(); cnt.pop(); vectordist2(n+1,-INF); dist2[idx]=0; queue

pq2;//to come pq2.push({idx,0}); while(!pq2.empty()){ auto [to,come]=pq2.front(); pq2.pop(); for(auto [v,cost]:g[to]){ if(v==come)continue; dist2[v]=dist2[to]+cost; pq2.push({v,to}); } } rep(i,1,n+1){ ans=max(ans,dist2[i]); cnt.push({dist2[i],i}); } clock_t end= clock(); if(end-start>1900)break; } cout<