#include<fstream>
#include<algorithm>
#include<vector>
#define nMax 200005
#define mMax 400005
#define INF 1 << 30
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int Vec[nMax], dist[nMax], heap[nMax], poz[nMax], Rez, k, nod, x, i, a, b, c, n, m, cost, j;
vector <pair <int, int> > G[nMax];
vector <pair <int, int> > Vect;
void upDate(int pozi)
{
    int po;
    while(pozi/2>0)
    {
        po=pozi/2;
        if(dist[heap[pozi]]<dist[heap[po]])
        {
            swap(poz[heap[po]], poz[heap[pozi]]);
            swap(heap[po], heap[pozi]);
            pozi=po;
        }
        else
            break;
    }
}
void inHeap(int node)
{
    heap[++k]=node;
    poz[node]=k;
    upDate(k);
}
void downDate(int pozi)
{
    int po;
    while(pozi*2<=k)
    {
        po=pozi*2;
        if(po+1<=k&&dist[heap[po+1]]<dist[heap[po]])
            po++;
        if(dist[heap[pozi]]>dist[heap[po]])
        {
            swap(poz[heap[po]], poz[heap[pozi]]);
            swap(heap[po], heap[pozi]);
            pozi=po;
        }
        else
            break;
    }
}
int awayHeap()
{
    int tata=heap[1];
    swap(poz[heap[1]], poz[heap[k]]);
    swap(heap[1], heap[k--]);
    downDate(1);
    poz[x]=0;
    return tata;
}
void inApm(int node)
{
    for(int j=0;j<G[node].size();j++)
    {
        nod=G[node][j].first;
        cost=G[node][j].second;
        dist[nod]=min(dist[nod], cost);
        if(dist[nod]==cost)
            Vec[nod]=node;
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].push_back(make_pair(b, c));
        G[b].push_back(make_pair(a, c));
    }
    for(i=1;i<=n;i++)
        dist[i]=INF;
    dist[1]=0, inApm(1);
    for(i=2;i<=n;i++)
        inHeap(i);
    for(i=1;i<n;i++)
    {
        x=awayHeap();
        inApm(x);
        Rez+=dist[x];
        Vect.push_back(make_pair(x, Vec[x]));
        for(j=0;j<G[x].size();j++)
        {
            nod=G[x][j].first;
            if(poz[nod])
                upDate(poz[nod]);
        }
    }
    fout<<Rez<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<Vect[i].first<<" "<<Vect[i].second<<'\n';
    return 0;
}