#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int a,b,c;
};
bool cmp(muchie a,muchie b)
{
    return a.c<b.c;
}
struct dsu
{
    vector<int> p;
    vector<int> sz;
    int n;
    dsu(int n)
    {
        this->n=n;
        p.resize(n+5);
        sz.resize(n+5);
        for(int i=1;i<=n;i++)
        {
            p[i]=i;
        }
    }
    int find_tata(int x)
    {
        if(x==p[x]) return x;
        p[x]=find_tata(p[x]);
        return p[x];
    }
    void unite(int a,int b)
    {
        int pa=find_tata(a);
        int pb=find_tata(b);
        if(sz[pa]<sz[pb])
        {
            swap(pa,pb);
        }
        p[pb]=pa;
        sz[pa]+=sz[pb];
    }
};
vector<muchie> v;
vector<pair<int,int>> w;
int main()
{
    int n,m,ans=0;
    fin>>n>>m;
    dsu DSU(n);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        v.push_back({a,b,c});
    }
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++)
    {
        int a=v[i].a;
        int b=v[i].b;
        int p1=DSU.find_tata(a);
        int p2=DSU.find_tata(b);
        if(p1==p2) continue;
        ans+=v[i].c;
        w.push_back({b,a});
        DSU.unite(a,b);
    }
    fout<<ans<<'\n'<<w.size()<<'\n';
    for(int i=0;i<w.size();i++)
    {
        fout<<w[i].first<<' '<<w[i].second<<'\n';
    }
    return 0;
}