#include using namespace std; #define int long long signed main(){ int n;cin>>n; vector>>connect(n); for(int i=0;i>a>>b>>c; a--;b--; connect[a].push_back({b,c}); connect[b].push_back({a,c}); } //関数の返り値->遠い奴のコストも一緒に const int inf=1e18; auto BFS=[&](auto BFS,int start)->pair{ vectorvis(n,false); vectordist(n,inf); dist[start]=0; priority_queue>que; que.push({0,start}); while(!que.empty()){ auto[w,now]=que.top(); que.pop(); if(vis[now])continue; if(w>dist[now])continue; vis[now]=true; for(auto[to,ww]:connect[now]){ if(!vis[to]){ if(dist[to]>dist[now]+ww){ dist[to]=dist[now]+ww; que.push({dist[to],to}); } } } } int ret=0,ret2=0; for(int i=0;i