#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n,m,apm,x,y,c;
vector <pair<int,pair<int,int>>> muchii;
vector <pair<int,int>> sol;
int t[200005];

int cauttata(int nod){
    if(t[nod]==0)
        return nod;
    t[nod] = cauttata(t[nod]);
    return t[nod];
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d", &n,&m);

    for(int i=0;i<m;++i){
        scanf("%d%d%d", &x,&y,&c);
        muchii.push_back({c,{x,y}});
    }
    sort(muchii.begin(),muchii.end());

    m=0;
    int tx, ty;

    for(auto i : muchii){
        if(m==n-1)
            break;

        tx = cauttata(i.second.first);
        ty = cauttata(i.second.second);

        if(tx!=ty){
            apm += i.first;
            t[tx] = ty;
            sol.push_back(i.second);
            ++m;
        }
    }

    cout<<apm<<"\n"<<n-1<<"\n";
    for(auto i : sol)
        cout<<i.first << " " << i.second <<"\n";

    return 0;
}