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

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 &);
};

void minheap(vector<pair<int,int> > &v,int i)
{
    int pmin;
    pair<int,int> aux;
    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].first<v[2*i+2].first) {
            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;
        minheap(v,pmin);
    }
    }
}

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

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

void graf::apm(char *numefis,const graf &x)
{
    vector <int> c,ci,t;
    vector <pair<int,int> > h;
    for (int i=0;i<n;i++)
    {
        ci.push_back(0);//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;
    t[0]=0;
    h.push_back(make_pair(c[0],ci[0]));
    int s=0,p=n;
    while (p>0)
    {
        while (ci[h[0].second]==1) decapitare(h);
        s+=h[0].first;
        u=h[0].second;
        cout<<"suma="<<s<<endl;
        cout<<"1"<<endl;
        for (int i=0;i<h.size();i++) cout<<h[i].first<<"-"<<h[i].second<<"-"<<ci[h[i].second]<<" ";
        decapitare(h);
        cout<<"2"<<endl;
        for (int i=0;i<h.size();i++) cout<<h[i].first<<"-"<<h[i].second<<"-"<<ci[h[i].second]<<" ";
        for (int i=0;i<c.size();i++)
        if (ci[i]==0 && a[u][i]!=0 && a[u][i]<c[i])
        {
            t[i]=u;
            c[i]=a[u][i];
            h.push_back(make_pair(c[i],i));
            minheap2(h,h.size()-1);
        }
        ci[u]=1;
        p--;
    }
    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;
}