#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int p[200005];
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
struct E{int x,y,c;};
vector<E> v;
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){int x,y,c;cin>>x>>y>>c;v.push_back({x,y,c});}
    sort(v.begin(),v.end(),[](const E&a,const E&b){return a.c<b.c;});
    for(int i=1;i<=n;i++)p[i]=i;
    long long sol=0;
    vector<pair<int,int>> ans;
    for(auto e:v){
        int rx=find(e.x),ry=find(e.y);
        if(rx!=ry){
            p[rx]=ry;
            sol+=e.c;
            ans.push_back({e.x,e.y});
        }
    }
    cout<<sol<<"\n"<<ans.size()<<"\n";
    for(auto e:ans)cout<<e.first<<" "<<e.second<<"\n";
    return 0;
}