#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

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

struct coord
{
    int x,y,cost;
};

bool fcmp(coord a, coord b)
{
    if(a.cost < b.cost)
    {
        return true;
    }
    return false;
}

int n,m;
int par[200005],ranc[200005];
coord v[400005];

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        v[i].x = x;
        v[i].y = y;
        v[i].cost = cost;
    }
}

int find(int nod)
{
    if(par[nod] == -1)
        return nod;
    return par[nod] = find(par[nod]);
}

void unite(int x, int y)
{
    int par1 = find(x);
    int par2 = find(y);
    if(par1 != par2)
    {
        if(ranc[par1] < ranc[par2])
            par[par1] = par2;
        else if(ranc[par1] > ranc[par2])
            par[par2] = par1;
        else
        {
            par[par2] = par1;
            ranc[par1]++;
        }
    }
}

void solve()
{
    vector<pair<int,int>> ans;
    long long suma = 0;
    sort(v+1,v+m+1,fcmp);   
    for(int i=1;i<=n;i++)
        par[i] = -1;
    for(int i=1;i<=m;i++)
    {
        int x = v[i].x;
        int y = v[i].y;
        int cost = v[i].cost;
        if(find(x) != find(y))
        {
            unite(x,y);
            suma = suma + cost;
            ans.push_back({x,y});
        }
    }
    g<<suma<<'\n';
    g<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++)
    {
        g<<ans[i].second<<" "<<ans[i].first<<"\n";
    }
}

int main()
{
    citire();
    solve();
}