#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<pair<int,int>,int> > v,solutie;
struct Dsu
{
    vector<int> p;
    vector<int> sz;
    Dsu(int n)
    {
        for ( int i = 0 ; i < n ; i++ )
            p.push_back(i),sz.push_back(1);
    }
    int Find(int x)
    {
        return (p[x]==x ? x : p[x] = Find(p[x])) ;
    }
    bool Check(int x,int y)
    {
        x = Find(x);
        y = Find(y);
        if ( x==y )
            return true;
        return false;
    }
    bool Union(int x,int y)
    {
        x = Find(x);
        y = Find(y);
        if ( x==y )
            return false;
        if ( x > y )
            swap(x,y);
        sz[x] += sz[y];
        sz[y] = 0 ;
        p[y] = x;
        return true;
    }
    void Reset(int n)
    {
        p.clear();
        sz.clear();
        for ( int i = 0 ; i < n ; i++ )
            p.push_back(i),sz.push_back(1);
    }
};


bool cmp(pair<pair<int,int>,int> v1,pair<pair<int,int>,int> v2)
{
    if(v1.second<v2.second)
    {
        return true;
    }
    else
        return false;
}


int main()
{
    int n,m,i,j,u,p,c;
    int costfin=0;
    fin>>n>>m;
    Dsu dsu(n+5);
    for(i=1;i<=m;++i)
    {
        fin>>u>>p>>c;
        v.push_back({{u,p},c});
    }
    sort(v.begin(),v.end(),cmp);
    for(i=0;i<m;++i)
    {
        if(dsu.Check(v[i].first.first,v[i].first.second))
            continue;
        solutie.push_back(v[i]);
        costfin+=v[i].second;
        dsu.Union(v[i].first.first,v[i].first.second);
    }
    fout<<costfin<<'\n'<<solutie.size()<<'\n';
    for(i=0;i<solutie.size();++i)
    {
        fout<<solutie[i].first.first<<' '<<solutie[i].first.second<<'\n';
    }
    return 0;
}