#include <bits/stdc++.h>
#define dm 200005
#define dm2 200005
std :: ifstream fin("apm.in");
std :: ofstream fout("apm.out");
using namespace std;
int n, m, arbcur;
int daddy[dm];
int x, y, cost, rez;
vector <int> v[dm];
struct str{
    int x;
    int y;
    int cost;
   /* bool operator < (const str &other)const{
        return cost > other.cost;
    }*/
}mch[dm2];
int root(int x)
{
    if(x == daddy[x])
        return x;
    else
        return daddy[x] = root(daddy[x]);
}
void add(int x, int y)
{
    int aux1 = root(x);
    int aux2 = root(y);
    daddy[aux2] = aux1;
}
bool cmp(str x, str y)
{
    if(x.cost < y.cost)
        return 1;
    return 0;
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> mch[i].x >> mch[i].y >> mch[i].cost;
    for(int i = 1; i <= n; i++)
        daddy[i] = i;
    sort(mch + 1, mch + m + 1, cmp);
    int it = 1;
    while(arbcur != n-1)
    {
        int x = mch[it].x;
        int y = mch[it].y;
        if(root(x) != root(y))
        {
            add(x, y);
            v[x].push_back(y);
            v[y].push_back(x);
            rez += mch[it].cost;
            arbcur++;
        }
        it++;
    }
    fout << rez << "\n" << n - 1 << "\n";
    for(int i = 0; i < n; i++)
    {
        for(auto it : v[i])
        {
            if( i < it)
            fout << i << " " << it << "\n";
        }
    }
    return 0;
}