#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 v[nmax], t[nmax], inH[nmax], heap[nmax], L, poz[nmax];
vector<pair<int, int> > g[nmax], sol;
int n, m;
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 introduceInAPM(int nod)
{
    vector<pair<int, int> >::iterator it;
    for(it=g[nod].begin(); it!=g[nod].end(); it++)
    {
        v[it->first]=min(v[it->first], it->second);
        if(v[it->first]==it->second)
            t[it->first]=nod;
    }
}
void heapUp(int p)
{
    while(p>1 && v[heap[p]]<v[heap[p/2]])
    {
        swap(heap[p], heap[p/2]);
        swap(poz[heap[p]], poz[heap[p/2]]);
        p/=2;
    }
}
void introduceInHeap(int nod)
{
    heap[++L]=nod;
    poz[nod]=L;
    heapUp(L);
}
void heapDown(int p)
{
    while((2*p<=L && v[heap[p]]>v[heap[2*p]]) || (v[heap[p]]>v[heap[2*p+1]] && 2*p+1<=L))
    {
        if((2*p<=L && v[heap[p]]>v[heap[2*p]]) || 2*p+1>L)
        {
            swap(heap[p], heap[2*p]);
            swap(poz[heap[p]], poz[heap[2*p]]);
            p=2*p;
        }
        else
        {
            swap(heap[p], heap[2*p+1]);
            swap(poz[heap[p]], poz[heap[2*p+1]]);
        }
    }
}
int radacina()
{
    int r;
    r=heap[1];
    swap(heap[1], heap[L]);
    swap(poz[heap[1]], poz[heap[L]]);
    L--;
    heapDown(1);
    poz[r]=0;
    return r;
}
void solve()
{
    int i, x, cost=0;
    vector<pair<int, int> >::iterator it;
    for(i=1; i<=n; i++)
        v[i]=inf;
    v[1]=0;
    introduceInAPM(1);
    for(i=2; i<=n; i++)
        introduceInHeap(i);
    for(i=1; i<n; i++)
    {
        x=radacina();
        introduceInAPM(x);
        cost+=v[x];
        sol.push_back(make_pair(x, t[x]));
        for(it=g[x].begin(); it!=g[x].end(); it++)
            if(poz[it->first])
                heapUp(poz[it->first]);
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(it=sol.begin(); it!=sol.end(); it++)
        fout<<it->first<<' '<<it->second<<'\n';
    fout.close();
}
int main()
{
    citire();
    solve();
    return 0;
}