#include <iostream>
#include <cstdio>
#include <vector>
#define Inf 1001
using namespace std;
vector<vector<pair<int, int> > > Graph(200001);
int N, M, i, j, Out;
struct Str{
    int cost;
    int nod1, nod2;
};
Str Cost[200001];
bool Check[200001];
pair<int, int> Sol[200001];
class Segm{
    int V[800001];
    void Change(int a, int b, int target, int position){
        int mid=(a+b)/2;
        if(a==b) {V[position]=target; return;}
        if(target<=mid) Change(a, mid, target, 2*position);
        else Change(mid+1, b, target, 2*position+1);
        if(Cost[V[2*position]].cost<Cost[V[2*position+1]].cost) V[position]=V[2*position];
        else V[position]=V[2*position+1];
        return;
    }
public:
    void Update(int target){
        Change(1, N, target, 1);
        return;
    }
    int top(){
        return V[1];
    }
};
Segm Tree;
void Add(int i);
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i) {Graph[i].push_back(make_pair(0, 0)); Cost[i].cost=Inf;}
    for(i=1; i<=M; ++i){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        Graph[x].push_back(make_pair(y, z));
        Graph[y].push_back(make_pair(x, z));
        ++Graph[x][0].first;
        ++Graph[y][0].first;
    }
    for(i=1; i<=N; ++i) Tree.Update(i);
    Check[1]=true;
    Add(1);
    for(i=1; i<N; ++i){
        int node=Tree.top();
        Out+=Cost[node].cost;
        Sol[i]=make_pair(Cost[node].nod1, Cost[node].nod2);
        Add(node);
        Check[node]=true;
        Cost[node].cost=Inf;
        Tree.Update(node);
    }
    printf("%d\n%d\n", Out, N-1);
    for(i=1; i<N; ++i) printf("%d %d\n", Sol[i].first, Sol[i].second);
    return 0;
}
void Add(int i){
    int j;
    for(j=1; j<=Graph[i][0].first; ++j){
        if(Check[Graph[i][j].first]==false && Cost[Graph[i][j].first].cost>Graph[i][j].second){
            Cost[Graph[i][j].first].cost=Graph[i][j].second;
            Cost[Graph[i][j].first].nod1=i;
            Cost[Graph[i][j].first].nod2=Graph[i][j].first;
            Tree.Update(Graph[i][j].first);
        }
    }
    return;
}