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

using namespace std;

class graf
{
    int m,n,**a;
public:
    graf(){m=0;n=0;a=NULL;}
    graf(const graf &x)
    {
        n=x.n;
        m=x.m;
        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;
            }
    };
    void apm(char *,const graf &);
    int t();
    ~graf(){delete [] a;};
    friend istream & operator >> (istream &,graf &);
    friend ostream & operator << (ostream &out,const graf &x);
};

int graf::t()
{
    cout<<"test";
    return 1;
}

void graf::apm(char *numefis,const graf &x)
{
    vector <int> c,t,q;
    for (int i=0;i<n;i++)
    {
        c.push_back(INT_MAX);
        t.push_back(0);
        q.push_back(0);
    }
    int u,min;
    c[0]=0;
    t[0]=0;
    int p=n,s=0;
    while (p!=0)
    {
        min=INT_MAX;
        for (int i=0;i<n;i++)
            if (c[i]<min && q[i]==0)
            {
                min=c[i];
                u=i;
            }
        for (int i=0;i<n;i++)
            if (a[u][i]!=0 && a[u][i]<c[i] && q[i]==0)
        {
            t[i]=u+1;
            c[i]=a[u][i];
        }
        q[u]=1;
        s+=c[u];
        p--;
    }
   ofstream f(numefis);
   f<<s<<endl<<n-1<<endl;
   for (int i=1;i<=n-1;i++)
   {
       f<<i+1<<" "<<t[i]<<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;
}

ostream & operator << (ostream &out,const graf &x)
{
    out<<x.n<<endl;
    for (int i=0;i<x.n;i++)
    {
        for (int j=0;j<x.n;j++)
            out<<x.a[i][j]<<" ";
        out<<endl;
    }
    return out;
}

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