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

using namespace std;

class graf
{
    int m,n;
    vector <vector<pair<int,int> > > a;
public:
    graf(){n=0;m=0;}
    graf(const graf &x)
    {
        n=x.n;
        m=0;
    };
    graf(int x)
    {
        n=x;
        m=0;
    };
    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);
        c.push_back(INT_MAX);
        t.push_back(0);
    }
    int u,min;
    c[0]=0;
    t[0]=0;
    h.push_back(make_pair(0,0));
    int s=0,p=n;
    for (int i=0;i<n;i++)
        for (int j=0;j<a[i].size();j++)
            cout<<i<<"-"<<a[i][j].first<<"-"<<a[i][j].second<<endl;
    while (p>0)
    {
        while (ci[h[0].second]==1) decapitare(h);
        s+=h[0].first;
        u=h[0].second;
        cout<<"1=";
        for (int i=0;i<h.size();i++) cout<<h[i].first<<"-"<<h[i].second<<" ";
        cout<<endl;
        decapitare(h);
        cout<<"2=";
        for (int i=0;i<h.size();i++) cout<<h[i].first<<"-"<<h[i].second<<" ";
        cout<<endl;
        for (int i=0;i<a[u].size();i++)
        if (ci[i]==0 && a[u][i].second<c[a[u][i].first])
        {
            t[a[u][i].first]=u;
            c[a[u][i].first]=a[u][i].second;
            h.push_back(make_pair(c[a[u][i].first],a[u][i].first));
            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.resize(x.n);
    int m,c,b,d;
    in>>x.m;
    m=x.m;
    while (m>0) {
        in>>b>>c>>d;
        x.a[b-1].push_back(make_pair(c-1,d));
        x.a[c-1].push_back(make_pair(b-1,d));
        m--;
    }
    return in;
}

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