#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

struct edges {int a,b,c;}aux;
int n,m,totalCost=0;

vector <edges> graph[400005], finalVersion;
priority_queue <edges> mainQueue;
vector <bool> visited;

ifstream fin("apm.in");
ofstream fout("apm.out");

bool operator<(const edges &x1,const edges &x2) {return x1.c>x2.c;} // Priority Queue

int main()
{
    fin >> n >> m;
    visited.resize(n+10,false);
    for(int i=m;i--;)
    {
        int u,v,cost;
        fin >> u >> v >> cost;
        aux.a = u;
        aux.b = v;
        aux.c = cost;
        graph[u].push_back(aux);
        aux.a=v;
        aux.b=u;
        graph[v].push_back(aux);
    }

    aux.a=1; aux.b=1; aux.c=0;
    mainQueue.push(aux);
    while(!mainQueue.empty())
    {
        aux= mainQueue.top(); mainQueue.pop();
        if(!visited[aux.b])
            {
            for(unsigned int i=0;i<graph[aux.b].size();i++)
                if(!visited[graph[aux.b][i].b])
                    mainQueue.push(graph[aux.b][i]);
            visited[aux.b]=true;
            totalCost += aux.c;
            finalVersion.push_back(aux);
            }

    }

    fout << totalCost << endl;
    fout << n-1 << endl;
    for(unsigned int i=0;i<finalVersion.size();i++)
        fout << finalVersion[i].a << " " << finalVersion[i].b << endl;

    return 0;
}