#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector< pair< int,int > >v[200002];
vector< pair< int,int> >sol;
int heap[200002],n,m,d[200002],l[200002],poz[200002],n_heap;

//in "heap" bagam nodurile
//in "d" avem distantele corespunzatoare fiecarui nod(la inceput le initializam cu infinit).
//in "poz[cv]" avem pozitia lui cv in heap
//in l tinem muchiile

void insertt(int x)
{
    while(x>1 && d[heap[x]]<d[heap[x/2]])
    {
        swap(poz[heap[x]],poz[heap[x/2]]);
        swap(heap[x],heap[x/2]);
        x/=2;
    }
}

void removee()
{
    swap(poz[heap[1]],poz[heap[n_heap]]);
    swap(heap[1],heap[n_heap]);
    heap[n_heap]=poz[heap[n_heap]]=0;
    n_heap--;
    int p=1,c=2;
    while(c<=n_heap)
    {
        if(c+1<=n_heap && d[heap[c+1]]<d[heap[c]])
            c++;
        if(d[heap[c]]<d[heap[p]])
        {
            swap(heap[c],heap[p]);
            swap(poz[heap[c]],poz[heap[p]]);
        }
        p=c;
        c=2*p;
    }
}

int main()
{
    int x,y,z,i,sum=0,j;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    for(i=1;i<=n;i++)
    {
        heap[i]=i;
        d[i]=INF;
        poz[i]=i;
    }
    d[1]=0;
    n_heap=n;
    while(n_heap!=0)
    {
        i=heap[1];
        sum+=d[i];
        if(l[i]!=0)
            sol.push_back(make_pair(l[i],i));
        removee();
        for(j=0;j<v[i].size();j++)
        {
            y=v[i][j].first;
            z=v[i][j].second;
            if(z<d[y])
            {
                d[y]=z;
                insertt(poz[y]);
                l[y]=i;
            }
        }
    }
    g<<sum<<'\n'<<sol.size()<<'\n';
    for(i=0;i<sol.size();i++)
        g<<sol[i].first<<" "<<sol[i].second<<'\n';
    return 0;
}