#include <bits/stdc++.h>

using namespace std;

#define TITLE "apm"

ifstream f (TITLE".in");
ofstream g (TITLE".out");

int Father[200002];
int Range[200002];

struct Muchie
{
    int Node1;
    int Node2;
    int Cost;
};

bool cmp(const Muchie &x, const Muchie &y)
{
    return x.Cost<y.Cost;
}

vector<Muchie> Muchii;

int Root(int Node)
{
    if(Father[Node]==Node)
        return Node;
    return Father[Node]=Root(Father[Node]);
}

void Union(int Root1, int Root2)
{
    if(Range[Root1]>Range[Root2])
        Father[Root2]=Root1;
    else
        Father[Root1]=Root2;
    if(Range[Root1]==Range[Root2])
        Range[Root1]++;
}

vector<pair<int,int>> answer;

int n;

void Kruskal()
{
    long long Sum=0;
    for(int i=1; i<=n; i++)
    {
        Father[i]=i;
        Range[i]=1;
    }
    for(auto it : Muchii)
    {
        int Root1=Root(it.Node1), Root2=Root(it.Node2);
        if(Root1!=Root2)
        {
            Sum+=it.Cost;
            answer.push_back({it.Node1,it.Node2});
            Union(Root1,Root2);
        }
    }
    g<<Sum<<'\n'<<n-1<<'\n';
    for(auto it : answer)
        g<<it.first<<' '<<it.second<<'\n';
}


int main()
{
    int m;
    f>>n>>m;
    while(m--)
    {
        Muchie a;
        f>>a.Node1>>a.Node2>>a.Cost;
        Muchii.push_back(a);
    }
    sort(Muchii.begin(),Muchii.end(),cmp);
    Kruskal();
    return 0;
}