#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <list>
#include <climits>

using namespace std;
#define inf INT_MAX/2
ifstream fin("apm.in");
ofstream fout("apm.out");

void citire(list <pair <int,int> > * &L,int &n,int &m)
{
    fin>>n>>m;
    L=new list<pair<int,int> >[n+1];
    int x,y,p;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>p;
        L[x].push_back({p,y});
        L[y].push_back({p,x});
    }

}

void initializare(vector <int> &tata,vector <int> &d,vector <int> &viz, int n,int s)
{
    int i;
    tata.resize(n+1);
    d.resize(n+1);
    viz.resize(n+1);
    for(i=1;i<=n;i++)
    {
        d[i]=inf;
        tata[i]=-1;
        viz[i]=0;
    }
    d[s]=0;

}
void Prim( list<pair<int,int> > *L,int n,int m, int st, vector <int> &tata,vector <int> &d,vector<int> &viz)
{
    int u,i,x,c;

    set<pair<int,int> > Q;
    initializare(tata,d,viz,n,st);

        Q.insert(make_pair(0,st));
    while(!Q.empty())
    {
        u=(*Q.begin()).second;
        c=(*Q.begin()).first;
        viz[u]=1;
        Q.erase(Q.begin());
        for(auto pr:L[u])
        {
            x=pr.second;
            c=pr.first;
            if(viz[x]==0 && d[x]>c)
            {
                d[x]=c;
                tata[x]=u;
                Q.insert(make_pair(d[x],x));
            }
        }


}
int sum=0;
 for(int i=1;i<=n;i++)
    {
        sum=sum+d[i];
    }
    fout<<sum<<endl;

fout<<n-1<<endl;
for(i=2;i<=n;i++)
    fout<<i<<" "<<tata[i]<<endl;

    }



int main()
{
    list <pair <int,int> > *L;
    int n,m,st;
    vector <int> tata;
    vector <int> d,viz;
    citire(L,n,m);

    Prim(L,n,m,1,tata,d,viz);
    return 0;
}