#include <bits/stdc++.h>

using namespace std;

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

int n,m,a[400001],parent[400001],cnt[400001];
long long s;
queue <pair<int,int>> q;

struct muchie
{
    int a,b,val;
}v[200001];

int cmp(muchie x,muchie y)
{
    return x.val<y.val;
}

int root(int x)
{
    if(parent[x] == x)
        return x;
    else
    {
        parent[x] = root(parent[x]);
        return root(parent[x]);
    }
}

void unire(int x, int y)
{
    int ra = root(x);
    int rb = root(y);
    if(ra == rb)
        return;
    if(cnt[ra] < cnt[rb])
        swap(ra,rb);
    parent[rb] = ra;
    cnt[ra] += cnt[rb];
}

int main()
{
    in>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,nr;
        in>>x>>y>>nr;
        v[i].a = x;
        v[i].b = y;
        v[i].val = nr;
    }
    sort(v+1,v+m+1, cmp);
    for(int i = 1;i<=n;i++)
        parent[i] = i,  cnt[i] = 1;
    int ok = 0;
    for(int i = 1;i<=m;i++)
    {
        if(root(v[i].a) != root(v[i].b))
        {
            unire(v[i].a,v[i].b);
            q.push(make_pair(v[i].a, v[i].b));
            s += v[i].val;
            ok++;
        }
        if(ok  == n-1)
            break;
    }
    out<<s<<"\n"<<n-1<<"\n";
    while(!q.empty())
    {
        out<<q.front().first<<" "<<q.front().second<<"\n";
        q.pop();
    }

    return 0;
}