/*

PRIM

d[i]=inf for i=1..n 
d[1]=0

d[] = costul minim de a adauga nodul i in arborele partial


L[1]= {(vecin,cost), ...}

PQ.push({-d[1],i})


pentru minimi
while(!PQ.empty())
{
    nod=PQ.top().second -> varful heapului -> 
    PQ.pop();
    if(viz[nod]==1)
    {
        continue;
    }
    sol+=d[nod];
    for(vecin in L[nod])
    {
        x=vecin.first
        cost=vecin.second
        if(d[x]>cost)
        {
            d[x]=cost;
            PQ.push({-d[x],x});
            parinte[x]=nod;
        }
    }
}

for(i=2..n)
    foot<(i,parinte[i])\n";




pentru retea cand m=n^2 folosim for pentru a gasi minimul
*/


#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");


#define INF 1001

int n,m;
int sol=0;
int k=0;


priority_queue<pair<int,int>> PQ; // max-heap; dam push {-cost,nod} ca sa fie min heap

vector <vector<pair<int,int>>> L; // lista de adiacenta
//L[x] = {(vecin,cost), (vecin,cost), ...}

vector <int> d;
vector <int> viz;
vector <int> parinte;

void citire()
{
    fin>>n>>m;

    L.resize(n+1);
    d.resize(n+1);
    viz.resize(n+1);
    parinte.resize(n+1);


    for(int i=1;i<=m;i++)
    {
        int x,y,cost;
        fin>>x>>y>>cost;
        L[x].push_back({y,cost});
        L[y].push_back({x,cost});
    }

    
}

void initalizare()
{


    for(int i=1;i<=n;i++)
    {
        d[i]=INF;
        viz[i]=0;
    }

    d[1]=0;

    PQ.push({-d[1],1});
}

void prim()
{
    while(!PQ.empty())
    {
        int nod=PQ.top().second;
        PQ.pop();

        if(viz[nod]==1)
            continue;
        
        sol+=d[nod];
        k++;
        viz[nod]=1;

        for(auto vecin:L[nod])
        {
            int x=vecin.first;
            int cost=vecin.second;
            if(d[x]>cost && viz[x]==0)
            {
                d[x]=cost;
                PQ.push({-d[x],x});
                parinte[x]=nod;
            }
        }
    }
}

int main()
{
    citire();
    initalizare();
    prim();
    fout<<sol<<"\n"<<k<<"\n";
    for(int i=2;i<=n;i++)
        fout<<i<<" "<<parinte[i]<<"\n";
    return 0;

}