#include <fstream>
#include <vector>
#include <set>
#include <bitset>

using namespace std;

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

const int nmax=2e5+1;

struct edge
{
    int u,v,cost;

    bool operator < (const edge &other) const
    {
        if(cost!=other.cost)
            return cost<other.cost;
        if(u!=other.u)
            return u<other.u;
        return v<other.v;
    }
};

set <edge> S;
vector<edge> mst;
int n,m,totalCost;
int trees[nmax];

void read()
{
    int u,v,cost;

    fin>>n>>m;

    for(int i=0;i<m;i++)
    {
        fin>>u>>v>>cost;

        S.insert({u,v,cost});
    }
}

void updateTrees(int u,int v)
{
    for(int i=1;i<=n;i++)
        if(trees[i]==trees[v] && i!=v)
            trees[i]=trees[u];
    trees[v]=trees[u];
}

void Kruskal()
{
    for(int i=1;i<=n;i++)
        trees[i]=i;

    int cnt=1;

    while(!S.empty() && cnt<n)
    {
        auto currentEdge=*S.begin();
        S.erase(S.begin());

        if(trees[currentEdge.u]!=trees[currentEdge.v])
        {
            cnt++;
            mst.emplace_back(currentEdge);
            totalCost+=currentEdge.cost;
            updateTrees(currentEdge.u,currentEdge.v);
        }
    }
}

void print()
{
    fout<<totalCost<<"\n"<<n-1<<"\n";
    for(auto it:mst)
        fout<<it.u<<" "<<it.v<<"\n";
}

int main()
{
    read();
    Kruskal();
    print();
    return 0;
}