#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int vmax=4e5;
int parent[vmax+1], status[vmax+1];
int n, m;
struct drum
{
    int x, y, c;
}d[vmax+1];
bool cmp(drum a, drum b)
{
    return (a.c<=b.c);
}
int findRoot(int nod)
{
    if(parent[nod]==nod)
        return nod;
    return parent[nod]=findRoot(parent[nod]);
}
void setUnion(int nod1, int nod2)
{
    nod1=findRoot(nod1);
    nod2=findRoot(nod2);
    if(nod1==nod2)
    {
        return ;
    }
    if(status[nod1]<status[nod2])
    {
        swap(nod1, nod2);
    }
    if(status[nod1]==status[nod2])
        status[nod1]++;
    parent[nod2]=nod1;
}
int main()
{
    in>>n>>m;
    for(int i=1; i<=n; i++)
    {
        parent[i]=i;
        status[i]=1;
    }
    for(int i=1; i<=m; i++)
    {
        in>>d[i].x>>d[i].y>>d[i].c;
    }
    sort(d+1, d+m+1, cmp);
    int rez=0, cnt=0;
    queue <pair<int, int>> q;
    for(int i=1; i<=m; i++)
    {
        if(findRoot(d[i].x)!=findRoot(d[i].y))
        {
            rez+=d[i].c;
            cnt++;
            q.push({d[i].x, d[i].y});
            setUnion(d[i].x, d[i].y);
        }
    }
    out<<rez<<'\n'<<cnt<<'\n';
    while(!q.empty())
    {
        out<<q.front().first<<" "<<q.front().second<<'\n';
        q.pop();
    }
}