#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector< vector< pair<int,int> > >graph;//graph[origine]=={destinatie,distanta_muchie}
vector<int>apm;//apm[fiu]==tata
vector<int>outside;//nod
vector<int>dist;
int m, n, tot;

int pop_outside(){
unsigned int i, imin=0;
int mn;
for( i = 0; i < outside.size(); i ++ )
    {if( dist[outside[i]] < dist[outside[imin]] )
        imin = i;
    }
mn = outside[imin];
outside[imin]=outside.back();
outside.pop_back();
return mn;
}

bool comp( const int&x, const int&y ){
if(dist[x]>dist[y])
    return true;
return false;
}



void prim(){
//make_heap( minHeap.begin(), minHeap.end(), comp );
unsigned int i,j;
int tempDist;
int curr;
while(!outside.empty())
    {
    curr = pop_outside();
    for( i = 0; i < graph[curr].size(); i ++ )//parcurgem nodurile adiacente celui curent;
        {
        for( j = 0; j < outside.size(); j ++ )//parcurgem nodurile din minHeap
            {
            if( outside[j] == graph[curr][i].first )//nodul adiacent este in minHeap
                {                                   //deci nu e in apm
                tempDist = graph[curr][i].second;//salvam distanta din nodul curent in cel adiacent
                if ( tempDist < dist[ outside[j] ] )//distanta calculata din nodul curent este mai mica decat cea calculata anterior
                    {dist[ outside[j] ] = tempDist;
                    apm[ outside[j] ] = curr;
                    //g<<"prin "<<curr+1<<" se ajunge mai repede in->"<<outside[j]+1<<"\n";
                    }
                break;
                }
            }
        }
    tot+=dist[ curr ];
    }

}


int main()
{
int x, y, z, i;
f >> n >> m;
graph.resize(n);
apm.resize(n,-2);
outside.resize(n);
for( i = 0; i < n; i ++ )
    {outside[i] = i;
    }
dist.resize(n,1 << 30);
dist[0]=0;
for( i = 0; i < m; i ++ )
    {f >> x >> y >> z;
    x --;
    y --;
    graph[x].push_back( make_pair(y,z) );
    graph[y].push_back( make_pair(x,z) );
    }

prim();
g<<tot<<"\n";
g<<n-1<<"\n";
for( i = 1; i < n; i ++ )
    {
    g<<i+1<<" "<<apm[i]+1<<"\n";

    }
f.close();
g.close();
return 0;
}