#include <fstream>
#include <vector>
#include <climits>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define nmax 200005
#define inf INT_MAX
int n, m, heap[2*nmax+100], l, c[nmax], ct, vec[nmax], poz[nmax];
vector<pair<int, int> > g[nmax], lst;
void citire()
{
    int i, x, y, c;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        g[x].push_back(make_pair(y, c));
        g[y].push_back(make_pair(x, c));
    }
    fin.close();
}
void heapUp(int k)
{
    while(k>1 && c[heap[k/2]]>c[heap[k]])
    {
        swap(heap[k], heap[k/2]);
        swap(poz[heap[k]], poz[heap[k/2]]);
        k/=2;
    }
}
void heapDown(int k)
{
    int fiu;
    fiu=2*k;
    while(fiu<=l)
    {
        if(fiu+1<=l)
            if(c[heap[fiu+1]]<c[heap[fiu]])
                fiu++;
        if(c[heap[fiu]]<c[heap[k]])
        {
            swap(heap[fiu], heap[k]);
            swap(poz[heap[fiu]], poz[heap[k]]);
        }
        else return;
        k=fiu;
        fiu=2*k;
    }
}
void heap_insert(int x)
{
    heap[++l]=x;
    poz[x]=l;
    heapUp(l);
}
int radacina()
{
    int r;
    r=heap[1];
    heap[1]=heap[l];
    l--;
    poz[heap[1]]=1;
    poz[r]=0;
    heapDown(1);
    return r;
}
void apmInsert(int x)
{
    vector<pair<int, int> >::iterator it;
    for(it=g[x].begin(); it!=g[x].end(); it++)
    {
        c[it->first]=min(c[it->first], it->second);
        if(c[it->first]==it->second)
            vec[it->first]=x;
    }
}
void solve()
{
    int i, x;
    vector<pair<int, int> >::iterator it;
    for(i=2; i<=n; i++)
        c[i]=inf;
    c[1]=0;
    apmInsert(1);
    for(i=2; i<=n; i++)
        heap_insert(i);
    for(i=1; i<n; i++)
    {
        x=radacina();
        apmInsert(x);
        ct+=c[x];
        lst.push_back(make_pair(x, vec[x]));
        for(it=g[x].begin(); it!=g[x].end(); it++)
            if(poz[it->first])
                heapUp(poz[it->first]);
    }
}
void afisare()
{
    vector<pair<int, int> >::iterator it;
    fout<<ct<<'\n'<<n-1<<'\n';
    for(it=lst.begin(); it!=lst.end(); it++)
        fout<<it->first<<' '<<it->second<<'\n';
    fout.close();
}
int main()
{
    citire();
    solve();
    afisare();
    return 0;
}