#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct MUCHIE
{
    int a,b,cost;
};
MUCHIE adj[400001];
int n,m;
int tati[200001];
int Rank[200001];
int parent(int i)
{
    if(tati[i]==i)
        return i;
    else
        return tati[i]=parent(tati[i]);
}
void Union(int a,int b)
{
    int pa = parent(a);
    int pb = parent(b);
    if(Rank[pa]==Rank[pb])
    {
        Rank[pa]++;
        tati[pb]=pa;
    }
    else if(Rank[pa]<Rank[pb])
        tati[pa]=pb;
    else
        tati[pb]=pa;
}
pair<int,int> sol[200000];
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>adj[i].a>>adj[i].b>>adj[i].cost;
    sort(adj+1,adj+m+1,[](const MUCHIE& a,const MUCHIE& b){return a.cost<b.cost;});
    int cost=0;
    for(int i=1;i<=n;i++)
        tati[i]=i;
    int k=0;
    for(int i=1;k!=n-1;i++)
    {
        if(parent(adj[i].a) != parent(adj[i].b))
        {
            Union(adj[i].a,adj[i].b);
            cost += adj[i].cost;
            sol[k++] = {adj[i].a,adj[i].b};
        }
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for(int i=0;i<k;i++)
        g<<sol[i].first<<' '<<sol[i].second<<'\n';
    f.close();
    g.close();
}