#include <bits/stdc++.h>
#define NMAX  400003

using namespace std;

struct muchie{
    int x,y,cost;
};

int n,m,sum;
muchie v[NMAX];
vector<int>sol;

class dsu{// disjoit set union
private:
    vector<int>parrent;
public:
    void make(int lg){
        parrent.resize(lg+2);
        for(int i=1;i<=lg;i++){
            parrent[i]=i;
        }
    }
    int Find(int nod){
        int root=nod;
        while(root!=parrent[root])
            root=parrent[root];
        while(nod!=root){
            int aux=parrent[nod];
            parrent[nod]=root;
            nod=aux;
        }
        return root;
    }
    void unite(int x,int y){
        parrent[Find(x)]=Find(y);
    }
}ds;

void get_apm(){// arbore partial cost minim
    // KRUSKAL
    for(int i=1;i<=m;i++){
        if(ds.Find(v[i].x)!=ds.Find(v[i].y)){ // daca nu sunt conectate
            ds.unite(v[i].x,v[i].y);
            sol.push_back(i);
            sum+=v[i].cost;
        }

    }

}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    ds.make(m);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
    }
    auto cmp=[](muchie a,muchie b){
        return a.cost<b.cost;
    };
    sort(v+1,v+m+1,cmp);
    get_apm();

    printf("%d\n",sum);
    printf("%d\n",(int)sol.size());
    for(int i=0;i<(int)sol.size();i++){
        int ind=sol[i];
        printf("%d %d\n",v[ind].x,v[ind].y);
    }

    return 0;
}