#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int v[400000][3];
int activate[400000];
int nodes[200001];
vector <int> graph[200001];
int visited[200001];

void myqsort(int beginus,int endus){
    int b=beginus,e=endus,pivot=v[(beginus+endus)/2][2],aux;
    if(b<=e){
        while(v[b][2]<pivot) b++;
        while(v[e][2]>pivot) e--;
        if(b<=e){
            aux=v[b][0]; v[b][0]=v[e][0]; v[e][0]=aux;
            aux=v[b][1]; v[b][1]=v[e][1]; v[e][1]=aux;
            aux=v[b][2]; v[b][2]=v[e][2]; v[e][2]=aux;
            b++; e--;
        }
    }
    if(beginus<e) myqsort(beginus,e);
    if(b<endus) myqsort(b,endus);
}

int isNotACycle(int a,int b){
    unsigned int i;
    int ceva=1;
    if(a==b) return 0;
    else{
        for(i=0;i<graph[a].size() && ceva!=0;i++){
            if(visited[graph[a][i]]==0){
                visited[graph[a][i]]=1;
                ceva=isNotACycle(graph[a][i],b);
                visited[graph[a][i]]=0;
            }
        }

        if(ceva==1) return 1;
        else return 0;
    }
}

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

    int n,m;
    fin>>n>>m;

    int i;
    for(i=0;i<m;i++)
        fin>>v[i][0]>>v[i][1]>>v[i][2];

    myqsort(0,m-1);

    int sum=0,nr=0;
    for(i=0;i<m;i++){
        visited[v[i][0]]=1;
        if(nodes[v[i][0]]==0 || nodes[v[i][1]]==0 || isNotACycle(v[i][0],v[i][1])){
            activate[i]=1;
            sum+=v[i][2];
            nr++;
            nodes[v[i][0]]++;
            nodes[v[i][1]]++;
            graph[v[i][0]].push_back(v[i][1]);
            graph[v[i][1]].push_back(v[i][0]);
        }
        visited[v[i][0]]=0;
    }

    fout<<sum<<endl<<nr<<endl;
    for(i=0;i<m;i++){
        if(activate[i]==1)
            fout<<v[i][0]<<" "<<v[i][1]<<endl;
    }

    fin.close();
    fout.close();
    return 0;
}