#include <bits/stdc++.h>

using namespace std;

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

int n,m,componente,costTotal;
typedef pair <int, pair< int, int > > ppair;
ppair muchie[400005]; ///X & Y & COST
vector< pair < int, int > >key,apm;  ///ID & nr elemente

struct comp{
        bool operator()(ppair m1, ppair m2){
            return (m1.second.second < m2.second.second);
        }
    };

int Find(int x)
{
    //cout<<"FIND:"<<x<<'\n';
    if(key[x-1].first!=x)key[x-1].first=Find(key[x-1].first);
    return key[x-1].first;
}

void Union(int x,int y)
{
    int xRoot=Find(x);
    int yRoot=Find(y);
    if(key[xRoot-1].second<key[yRoot-1].second){
        key[yRoot-1].second+=key[xRoot-1].second;
        key[xRoot-1].first=key[yRoot-1].first;
    }
    else{
        key[xRoot-1].second+=key[yRoot-1].second;
        key[yRoot-1].first=key[xRoot-1].first;
    }
    --componente;
}

int main()
{
    f>>n>>m;
    for(int i=0;i<m;++i){
        f>>muchie[i].first>>muchie[i].second.first>>muchie[i].second.second;
    }

    for(int i=1;i<=n;++i)key.push_back(make_pair(i,1));
    componente=n;
    sort(muchie,muchie+m,comp());

    for(int i=0;i<m;++i){
        if(componente==1)break;
        int x=muchie[i].first;
        int y=muchie[i].second.first;
        int cost=muchie[i].second.second;

        if(Find(x)!=Find(y)){
            Union(x,y);
            costTotal+=cost;
            apm.push_back(make_pair(x,y));
        }
    }

    g<<costTotal<<'\n'<<n-1<<'\n';
    for(auto x:apm)
        g<<x.second<<' '<<x.first<<'\n';


    f.close(); g.close();
    return 0;
}