#include <fstream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

typedef tuple<int,int,int> tp;

const int MAX_NODES=2e5;

int parent[MAX_NODES+5];
int level[MAX_NODES+5];
set <tp> Edges;
vector<pair<int,int>> MST;

int gaseste_multime(int i)
{
    if(parent[i]==i)return i;
    else
    {
        gaseste_multime(parent[i]);
    }
}

void uneste_multimi(int x,int y)
{
   int multimeX=gaseste_multime(x);
   int multimeY=gaseste_multime(y);
   if(multimeX!=multimeY)
   {
       if(level[multimeX]<level[multimeY])parent[multimeX]=multimeY;
       else if(level[multimeY]<level[multimeX])parent[multimeY]=multimeX;
       else {parent[multimeY]=multimeX;level[multimeX]++;}
   }


}

int main()
{
 int n,m;

 fin>>n>>m;

while(m--)
{   int x,y,cost;
    fin>>x>>y>>cost;
    Edges.insert({cost,x,y});
}

for(int i=1;i<=n;i++)
{
    parent[i]=i;
    level[i]=1;
}
int sol=0;
for(auto &[cost,x,y]: Edges)
{

    int X=gaseste_multime(x);
    int Y=gaseste_multime(y);
    if(X==Y)continue;
    sol+=cost;
    uneste_multimi(x,y);
    MST.push_back({x,y});


}
fout<<sol<<"\n"<<MST.size()<<"\n";
for(int i=0;i<MST.size();i++)
{
    fout<<MST[i].first<<" "<<MST[i].second<<"\n";
}
    return 0;
}