#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct e{
int x, y;
int cost;
int t,c;
};
bool cmp(e x, e y){
return x.cost < y.cost;
}
int n, m, x, y, c, todo, p[100000];
long long ans;
int find(int a){
if (p[a] == a) return a;
else {
p[a] = find(p[a]);
return p[a];
}
}
vector <e> v;
long long int ans1=0,ans2=0;
vector<pair<int,int> >ch;
int main() {
while (cin >> n >> m){
todo = n-1;
ans = 0;
v.clear();
for (int i = 0; i < n; i++){
p[i] = i;
}
for (int i = 0; i < m; i++){
int o,p;
cin >> x >> y >> o>>p;
v.push_back({x, y, o*p,o,p});
}
sort(v.begin(), v.end(), cmp);
for (int i=0;i<v.size();i++){
x = find(v[i].x);
y = find(v[i].y);
if (x == y) continue;
else {
p[y] = x;
todo -= 1;
ch.push_back(make_pair(v[i].x,v[i].y));
ans1 += v[i].t;
ans2 += v[i].c;
}
}
if (todo == 0) cout << ans1 <<" "<<ans2<< "\n";
else cout << "-1\n";
for(int i=0;i<ch.size();i++){
cout<<ch[i].first<<" "<<ch[i].second<<endl;
}
}
return 0;
}
/*
5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |