#include <iostream>
#include <vector>
#include <limits.h>
#include <string>
#include <fstream>
#include <algorithm>

using namespace std;

class graf
{
    int m,n;
    int **a;
public:
    graf(){n=0;a=NULL;m=0;}
    graf(const graf &x)
    {
        n=x.n;
        m=0;
        a=new int *[n];
        for (int i=0;i<n;i++)
            {
                a[i]=new int[n];
                for (int j=0;j<n;j++) a[i][j]=x.a[i][j];
            }
    };
    graf(int x)
    {
        n=x;
        m=0;
        a=new int *[n];
        for (int i=0;i<n;i++)
            {
                a[i]=new int[n];
                for (int j=0;j<n;j++) a[i][j]=0;
            }
    };
    ~graf(){delete [] a;};
    void apm(char *,const graf &);
    friend istream & operator >> (istream &,graf &);
};

bool comp(pair<int,int> a,pair<int,int> b)
{
    if (a.first<b.first) return false;
    return true;
}

void minheap2(vector<int> &v,vector<int> &p,int i)
{
    if (i!=0)
    {
    if (i%2==0 && v[(i-1)/2]>v[i])
    {
        int aux=v[(i-1)/2];
        v[(i-1)/2]=v[i];
        v[i]=aux;
        aux=p[(i-1)/2];
        p[(i-1)/2]=p[i];
        p[i]=aux;
        minheap2(v,p,(i-1)/2);
    }
        else if (i%2==1 && v[i/2]>v[i])
        {
            int aux=v[i];
            v[i]=v[i/2];
            v[i/2]=aux;
            aux=p[i];
            p[i]=p[i/2];
            p[i/2]=aux;
            minheap2(v,p,i/2);
        }
    }
}

void minheap(vector<int> &v,vector<int> &p,int i)
{
    int aux,pmin;
    if ((2*i+1)<v.size()) {
    if ((2*i+2)==v.size()) {
        pmin=2*i+1;
        aux=v[2*i+1];
    }
        else if (v[2*i+1]<v[2*i+2]) {
            pmin=2*i+1;
            aux=v[2*i+1];
        }
            else {
                pmin=2*i+2;
                aux=v[2*i+2];
            }
    if (v[i]>aux) {
        v[pmin]=v[i];
        v[i]=aux;
        aux=p[pmin];
        p[pmin]=p[i];
        p[i]=aux;
        minheap(v,p,pmin);
    }
    }
}

void asambleaza(vector<int> &v,vector<int> &p)
{
    int i;
    for (i=v.size()/2-1;i>=0;i--) minheap(v,p,i);
}

void decapitare(vector<int> &v,vector<int> &p)
{
    int aux;
    aux=v[v.size()-1];
    v[v.size()-1]=v[0];
    v[0]=aux;
    aux=p[v.size()-1];
    p[v.size()-1]=p[0];
    p[0]=aux;
    v.erase(v.end()-1);
    p.erase(p.end()-1);
    //minheap(v,p,0);
}

void graf::apm(char *numefis,const graf &x)
{
    vector <int> c,ci,t;
    for (int i=0;i<n;i++)
    {
        ci.push_back(i);//ci reprezinta pentru c[i] varful care are costul c[i]
        c.push_back(INT_MAX);
        t.push_back(0);
    }
    int u,min;
    c[0]=0;
    ci[0]=0;
    t[0]=0;
    int s=0;
    while (!c.empty())
    {
        s+=c[0];
        u=ci[0];
        c.erase(c.begin());
        ci.erase(ci.begin());
        for (int i=0;i<ci.size();i++)
            if (a[u][ci[i]]!=0 && a[u][ci[i]]<c[i])
        {
            t[ci[i]]=u;
            c[i]=a[u][ci[i]];
            minheap2(c,ci,i);
        }
        //decapitare(c,ci);
        //asambleaza(c,ci);
    }
    ofstream f(numefis);
    f<<s<<endl<<n-1<<endl;
    for (int i=1;i<=n-1;i++)
    {
        f<<i+1<<" "<<t[i]+1<<endl;
    }
}

istream & operator >> (istream &in,graf &x)
{
    in>>x.n;
    x.a=new int*[x.n];
    for (int i=0;i<x.n;i++) {
        x.a[i]=new int[x.n];
        for (int j=0;j<x.n;j++) x.a[i][j]=0;
    }
    int m,c,b,d;
    in>>x.m;
    m=x.m;
    while (m>0) {
        do {
        in>>b>>c>>d;
        if (x.a[b-1][c-1]>0) cout<<"Aceasta muchie a fost deja adaugata!"<<endl;
        } while (x.a[b-1][c-1]>0);
        x.a[b-1][c-1]=d;
        x.a[c-1][b-1]=d;
        m--;
    }
    return in;
}

int main()
{
    graf x;
    ifstream f("apm.in");
    f>>x;
    x.apm("apm.out",x);
    return 0;
}