#include <bits/stdc++.h>
#define lim 400009

using namespace std;

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

int n, m, tat[lim/2], rang[lim/2], costtotal;

pair <int, int> vfinal[lim/2];

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

nod v[lim];

bool compara(nod a, nod b)
{
    return a.cost < b.cost;
}

void read()
{
    in>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        in>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1, v+m+1, compara);
    for(int i=1; i<=n; ++i)
    {
        tat[i]=i;
        rang[i]=0;
    }
}

int findtat(int x)
{
    while(tat[x]!=x)
        x=tat[x];
    return x;
}

void unire(int x, int y)
{
    if(rang[x]>rang[y])
    {
        tat[y]=x;
    }
    else
    {
        tat[x]=y;
        if(rang[x]==rang[y])
            rang[y]++;
    }
}

void kruskal()
{
    int nr=0;
    for(int i=1; i<=m; ++i)
    {
        int a=findtat(v[i].x);
        int b=findtat(v[i].y);
        if(a!=b)
        {
            vfinal[++nr].first=v[i].x;
            vfinal[nr].second=v[i].y;
            unire(a,b);
            costtotal+=v[i].cost;
        }
    }
}

void print()
{
    out<<costtotal<<'\n'<<n-1<<'\n';
    for(int i=1; i<n; ++i)
    {
        out<<vfinal[i].first<<" "<<vfinal[i].second<<'\n';
    }
}

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