#include <bits/stdc++.h>

using namespace std;

#define NMAX 500
#define ll long long int



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

vector<pair<int,pair<int,int>>> edges;
int t[200001],r[200001];
int n,m;

bool cmp(pair<int,pair<int,int>> a,pair<int,pair<int,int>> b)
{
    return a.first < b.first;
}
int root(int x)
{
    if(t[x]==x)
    {
        return x;
    }
    t[x]=root(t[x]);
    return t[x];
}
int main()
{
    fin >> n >> m;
    while(m--)
    {
        int a,b,c;
        fin >> a >> b >> c;
        edges.push_back({c,{a,b}});
    }
    sort(edges.begin(),edges.end(),cmp);

    for(int i=1;i<=n;i++)
    {
        t[i]=i;
        r[i]=1;
    }
    vector<pair<int,pair<int,int>>> res;
    for(auto i : edges)
    {
        int c = i.first;
        int a = i.second.first,b=i.second.second;
        a=root(a),b=root(b);

        if(a!=b)
        {
            t[b]=a;
            res.push_back(i);
        }
    }
    int tot=0;
    for(auto i : res)
    {
        tot += i.first;
    }
    fout << tot << "\n" << res.size() << "\n";
    for(auto i : res)
    {
        fout << i.second.first << " " << i.second.second << "\n";
    }
}