#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
struct graf{
int x,y,cost;
}v[400005];
bool way_to_sort(graf &i,graf &j)
{
    return i.cost<=j.cost;
}
vector <graf> a;
int t[200005];
void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1,v+m+1,way_to_sort);
     for(int i =1 ; i <= n ; i++)
        t[i] = i;
     int S = 0, cnt = 0;
     for(int i = 0 ; i <= m && cnt < n ; i ++)
        if(t[v[i].x] != t[v[i].y])
        {
            S += v[i].cost;
            cnt++;
            a.push_back(v[i]);
            int ai = t[v[i].x], aj = t[v[i].y];
            for(int j =1 ; j <= n ; ++j)
                if(t[j] == aj)
                    t[j] = ai;
        }
    fout << S << "\n"<<a.size()<<"\n";
    for(unsigned int i=0;i<a.size();i++)
    {
        fout<<a[i].x<<' '<<a[i].y<<endl;
    }
}
int main()
{
    citire();
}