#include <fstream>
#include <vector>
using namespace std;
#define DMAX 200005
#define INF 999999999
ifstream fin("apm.in");
ofstream fout("apm.out");
typedef pair<int,int> pr;
vector <pr> matrice[DMAX];
int n,m;
int heapsize,heap[DMAX],poz[DMAX],dist[DMAX],tata[DMAX],use[DMAX],cost;
void citire();
void insereaza(int nod);
void ridica(int c);
void schimba(int a,int b);
int extrage_rad();
void prim(int nod);
void afisare();
int main()
{
    citire();
    prim(1);
    afisare();
    return 0;
}
void prim(int nod)
{
    int i;
    for(i=1;i<=n;i++)
    {
        dist[i]=INF;
        tata[i]=nod;
    }
    tata[nod]=0;
    dist[nod]=0;
    insereaza(nod);
    while(heapsize!=0)
    {
        int node=extrage_rad();
        use[node]=1;
        for(i=0;i<matrice[node].size();++i)
        {
            int ind=matrice[node][i].first;
            int c=matrice[node][i].second;
            if(dist[ind]>c&&use[ind]==0)
            {
                if(dist[ind]==INF)
                {
                    dist[ind]=c;
                    insereaza(ind);
                }
                 else
                {
                    dist[ind]=c;
                    ridica(poz[ind]);
                }
            }
            tata[ind]=node;
        }
    }
    for(int i=1;i<=n;++i) cost+=dist[i];
}
void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        matrice[a].push_back(make_pair(b,c));
        matrice[b].push_back(make_pair(a,c));
    }
}
void afisare()
{
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(int i=2;i<=n;i++)
    {
        fout<<i<<' '<<tata[i]<<'\n';
    }
}
void insereaza(int nod)
{
    heap[++heapsize]=nod;
    poz[nod]=heapsize;
    ridica(heapsize);
}
void ridica(int c)
{
    int p;
    p=c/2;
    while(c>1&&dist[heap[p]]>dist[heap[c]])
    {
        schimba(p,c);
        c=p;
        p=c/2;
    }
}
void cerne(int p)
{
    int c=p*2;
    while(c<=heapsize)
    {
        if(c!=heapsize)
            if(dist[heap[c]]>dist[heap[c+1]])
                c++;
        if(dist[heap[p]]>dist[heap[c]])
            {
                schimba(c,p);
                p=c;
                c=p*2;
            }
        else break;
    }
}
int extrage_rad()
{
    int root=heap[1];
    schimba(1,heapsize);
    poz[heap[heapsize--]]=0;
    cerne(1);
    return root;
}
void schimba(int a,int b)
{
    swap(poz[heap[a]],poz[heap[b]]);
    swap(heap[a],heap[b]);
}