#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxN=2e5+1;
const int maxEdges=4e5+1;

struct Edge{
    int x,y;
    int cost;
    bool operator <(const Edge &alt){
        return cost<alt.cost;
    }
}edges[maxEdges];

int t[maxN];
int sz[maxN];

int findDSU(int x){
    if(t[x]!=x)
        return t[x]=findDSU(t[x]);
    return t[x];
}

void uniteDSU(int x,int y){
    int tx=findDSU(x);
    int ty=findDSU(y);

    if(tx==ty){
        return;
    }

    if(sz[tx]<sz[ty]){
        t[tx]=ty;
        sz[ty]+=sz[tx];
    } else {
        t[ty]=tx;
        sz[tx]+=sz[ty];
    }
}

int n,m;

int main(){
    ifstream f("apm.in");
    ofstream g("apm.out");

    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>edges[i].x>>edges[i].y>>edges[i].cost;
    }

    sort(edges+1,edges+m+1);

    int cnt=0;
    long long apmCost=0;
    vector<Edge> apm;

    for(int i=1;i<=n;i++){
        t[i]=i;
        sz[i]=1;
    }

    for(int i=1;i<=m && cnt<n;i++){
        int x=edges[i].x;
        int y=edges[i].y;
        int cost=edges[i].cost;

        if(findDSU(x)!=findDSU(y)){
            uniteDSU(x,y);
            cnt++;
            apmCost+=cost;
            apm.push_back(edges[i]);
        }
    }

    g<<apmCost<<'\n'<<n-1<<'\n';
    for(int i=0;i<apm.size();i++){
        g<<apm[i].x<<" "<<apm[i].y<<'\n';
    }

    return 0;
}