#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX=200005, MMAX=400005;

struct edge{
    int a, b, c;
}muc, edges[MMAX];

bool comp(edge a, edge b){
    return a.c<b.c;
}

int n, m, x, y, z, sum;

vector <pair <int,int>> parent(NMAX,{-1,1}), r;

int find_root(int x){
    if(parent[x].first==-1){
        return x;
    }
    return parent[x].first=find_root(parent[x].first);
}

void union_sets(int a, int b){
    a=find_root(a);
    b=find_root(b);

    if(parent[a].second<parent[b].second)
        swap(a,b);
    if(parent[a].second==parent[b].second)
        parent[a].second++;
    parent[b].first=a;
}

int main(){
    fin>>n>>m;
    for(int i=0;i<m;i++){
        fin>>edges[i].a>>edges[i].b>>edges[i].c;
    }
    sort(edges, edges+m, comp);
    for(int i=0;i<m;i++){
        int nod1=edges[i].a;
        int nod2=edges[i].b;

        if(find_root(nod1)!=find_root(nod2)){
            union_sets(nod1,nod2);
            sum+=edges[i].c;
            r.push_back({nod1,nod2});
        }
    }
    fout<<sum<<endl<<n-1<<endl;
    for(int i=0;i<n-1;i++){
        fout<<r[i].first<<' '<<r[i].second<<endl;
    }
    return 0;
}