#include <iostream>
#include <vector>
#define inf 100009
#define nmax 10000
#include <fstream>

using namespace std;
ifstream f("primI.txt");

int n,m;
int verificare(int* g,int *viz)
{
    int i;
    int ok=0;
    for(i=1; i<=n; i++)
        if(viz[i]!=0)
            ok=1;
    return ok;
}

int extract_min(int* q,int* viz,int* key)
{
    int i;
    int mn=inf,vf=0;
    for(i=1; i<=n; i++)
        if(key[i]<mn && viz[i]!=0)
        {
            mn=key[i];
            vf=i;
        }
    viz[vf]=0;
    return vf;
}
int cost=0;
void Prim(int** g,int r,int* viz,int* q,int* key,int *pi)
{
    int i;
    key[r]=0;
    while(verificare(q,viz)==1)
    {
        int  u=extract_min(q,viz,key);
        for(int j=1; j<=n; j++)
            if(g[u][j]!=0)
                if(viz[j]!=0 && g[u][j]<key[j])
                {
                    pi[j]=u;
                    //cout<<"O muchie: "<<u<<" "<<j<<endl;
                    //cost+=g[u][j];
                    key[j]=g[u][j];
                }
    }

}
int cost1=0;
int k;
void afisare(int**g,int* p,int i)
{
    if(i<=n)
    {
        if(p[i]!=0)
        {
            cost1+=g[p[i]][i];
            k++;
        }
        afisare(g,p,i+1);
        if(p[i]!=0)
            cout<<p[i]<<" "<<i<<endl;
    }
    else
    {
        cout<<cost1<<endl;
        cout<<k<<endl;
    }
}
int main()
{
    int x,y,z;
    f>>n>>m;
    //cout<<n<<" "<<m<<endl;

    int *viz=new int[n];
    int *pi=new int[n];
    int *q=new int[n];
    int *key=new int[n];
    int **g=new int*[n];
    //cout<<"alocat";
    for(int i=1; i<=n; i++)
        g[i]=new int[n];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            g[i][j]=0;
    for(int i=1; i<=n; i++)
    {
        viz[i]=1;
        key[i]=inf;
        pi[i]=0;
        q[i]=i;
    }
    while(m!=0)
    {
        m--;
        f>>x>>y>>z;
        g[x][y]=z;
        g[y][x]=z;
    }
    //cout<<"citit";
    Prim(g,1,viz,q,key,pi);
    //cout<<"gata prim";
    /* cout<<cost<<endl;*/
     /*for(int i=1; i<=n; i++)
         if(pi[i]!=0)
             cout<<pi[i]<<" "<<i<<endl;
     cout<<endl<<endl;*/
    afisare(g,pi,1);
    delete []viz;
    delete []pi;
    delete []key;
    delete []q;
    for(int i=1; i<=n; i++)
        delete []g[i];

    delete []g;
    return 0;
}