#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int p[200005];
struct Edge{
    int u,v,w;
};
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
void make_set(int n){
    for(int i =1;i<=n;i++)p[i]=i;
}
int find_set(int u){
    if(u==p[u])return u;
    return p[u]=find_set(p[u]);
}
bool unite_sets(int a,int b){
    a=find_set(a);
    b=find_set(b);
    if(a!=b){
        p[b]=a;
        return true;
    }
    return false;
}
int main(){
    int n,m;
    fin>>n>>m;
    vector<Edge> edges(m);
    for(int i =0;i<m;i++){
        int u,v,w;
        fin>>u>>v>>w;
        Edge a;
        a.u=u;
        a.v=v;
        a.w=w;
        edges[i]=a;
    }
    sort(edges.begin(),edges.end(),cmp);
    int res=0;
    make_set(n);
    vector<pair<int,int>> c;
    for(int i=0;i<m;i++){
        int u=edges[i].u;
        int v=edges[i].v;
        int w=edges[i].w;
        if(unite_sets(u,v)){
            res+=w;
            c.push_back({u,v});
        }
    }
    fout<<res<<"\n"<<n-1<<"\n";
    for(int i =0;i<n-1;i++){
        fout<<c[i].first<<" "<<c[i].second<<"\n";
    }
    return 0;
}