#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
#define MAXN 200005
using namespace std;

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

struct edge
{
    int firstVertex, secondVertex;
    int cost;
    bool operator < (const edge &other) const
    {
        return (cost>other.cost);
    }
};

priority_queue<edge> Edges;
vector <pair <int,int> > Graph[MAXN];
vector<edge> Solution;

int n,m;
int cost[MAXN];
int daddy[MAXN];
bool inTree[MAXN]={false};
int minimumCost=0;
void initialize(int startNode)
{
    for(int i=1;i<=n;i++)
        cost[i]=INF;
    for(auto &e:Graph[startNode])
    {
        daddy[e.first]=startNode;
        cost[e.first]=e.second;
        Edges.push({startNode, e.first, e.second});
    }
    inTree[startNode]=true;
}
void prim(int startNode)
{
    initialize(startNode);
    while(!Edges.empty())
    {
        edge minimumEdge=Edges.top();
        Edges.pop();
        if(!inTree[minimumEdge.secondVertex])
        {
            minimumCost+=minimumEdge.cost;
            inTree[minimumEdge.secondVertex]=true;
            Solution.push_back(minimumEdge);
            for(auto &e:Graph[minimumEdge.secondVertex])
                if(!inTree[e.first]&&cost[e.first]>e.second)
                {
                    Edges.push({minimumEdge.secondVertex, e.first, e.second});
                    cost[e.first]=e.second;
                    daddy[e.first]=minimumEdge.secondVertex;
                }
        }
    }
}
void printSolution()
{
    fout<<minimumCost<<"\n";
    fout<<n-1<<"\n";
    for(auto &e:Solution)
        fout<<e.firstVertex<<" "<<e.secondVertex<<"\n";
}
void read()
{
    fin>>n>>m;
    int x,y;
    int c;
    for(int q=0;q<m;++q)
        fin>>x>>y>>c, Graph[x].push_back({y,c}), Graph[y].push_back({x,c});
    prim(1);
    printSolution();
}
int main()
{
    read();
    return 0;
}