#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define mp make_pair
#define pb push_back
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,p[200002],s,t;
vector <pair<int,pair <int,int> > > v;
vector <int >sol;
void citire()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v.pb(mp(c,mp(a,b)));
    }
}
int findx(int x)
{
    if(p[x]<0)
        return x;
    else
        return findx(p[x]);
}
void unionx(int a,int b)
{
    int parenta =findx(a);
    int parentb =findx(b);
    if(p[parenta]>p[parentb])
        p[parenta]=parentb;
    else if(p[parenta]<p[parentb])
        p[parentb]=parenta;
    else
    {
        p[parenta]=parentb;
        p[parentb]--;
    }
}
void APM()
{
    for(int i=1;i<=n;i++)
        p[i]=-1;
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)
    {
        int x=findx(v[i].second.first);
        int y=findx(v[i].second.second);
        if(x!=y)
        {
            s+=v[i].first;
            unionx(x,y);
            sol.pb(v[i].second.second);
            sol.pb(v[i].second.first);
            t+=2;
        }
        if(t/2==n-1)
            break;

    }
    fout<<s<<'\n'<<t/2<<'\n';
    for(int i=0;i<sol.size();i++)
    {
        fout<<sol[i]<<" "<<sol[i+1]<<'\n';
        i++;
    }
}
int main()
{
    citire();
    APM();
    return 0;
}