#include #include #include #include using namespace std; vector > G[100005]; int n,k; #define MAXN 100005 typedef int var; int grade[100005],tati[100005]; vector costs; void read() { cin>>n>>k; for(int i=0; i>a>>b>>c; G[a].push_back({b,c}); G[b].push_back({a,c}); grade[a]++; grade[b]++; if(a>b) swap(a,b); tati[b]=a; } tati[1]=0; } const int64_t INF = 1e9; void dijkstra(int start) { vector dist(n+1,INF); dist[start]=0; int u; set > s; s.insert({dist[start], start}); while(!s.empty()) { u = s.begin() -> second; s.erase(s.begin()); for(auto p : G[u]) if(dist[p.first]>dist[u]+p.second) { s.erase({dist[p.first],p.first}); dist[p.first]=dist[u]+p.second; s.insert({dist[p.first],p.first}); } } for(int y=start+1; y<=n; y++) if(y!=start && dist[y]!=INF) costs.push_back(dist[y]); /* for(auto x:G[start]) { int i=x.first; for(int j=0;j1) dijkstra(i); sort(begin(costs),end(costs)); if(k>costs.size()) cout<<"-1"; else cout<