#include <bits/stdc++.h>
#define N 200007
using namespace std;

int n,m;
int radacina[N];
int cost;
vector<pair<int,int>> ans;
vector<pair<int,pair<int,int>>> muchii;

int  Find(int x)
{
    if( !radacina[x] )
        return x;
    radacina[x] = Find( radacina[x] );
    return radacina[x];
}
void Union(int x,int y)
{
    int ty=Find(y);
    int tx=Find(x);
    if( ty!=tx )
        radacina[ tx ]=ty;
}

int main()
{
    ifstream fin("apm.in");ofstream fout("apm.out");
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        muchii.push_back( {c,{x,y}} );
    }
    sort(muchii.begin(),muchii.end());
    for(int i=0;i<m;i++)
    {
        int x,y;
        x=muchii[i].second.first;
        y=muchii[i].second.second;
        if( Find(x)!=Find(y) )
        {
            cost+= muchii[i].first;
            Union( x,y );
            ans.push_back( {x,y} );
        }
    }
    fout << cost << "\n" << n-1 << "\n";
    for(int i=0;i<n-1;i++)
        fout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}