#include <bits/stdc++.h>

#ifndef LOCAL
    #pragma GCC optimize("Ofast")
    //#pragma GCC target("avx2")
#endif // LOCAL

#define all(x) x.begin(),x.end()

using namespace std;


#ifndef LOCAL
    string name="apm";
    ifstream in(name+".in");
    ofstream out(name+".out");
    #define cin in
    #define cout out
#endif // LOCAL



const int MN = 200005;
const int MM = 400005;
const int MV = 2005;

using pii = pair<int,int>;
using vvi = vector<vector<int>>;
using vvp = vector<vector<pii>>;
using vi = vector<int>;


struct edge{
  int a,b,c;  
} ed[MM];



vvi mst;
vi col, min_ed;
int n,m;
void dfs(int nod)
{
    assert(col[nod]!=0);
    
    for(auto e:mst[nod])
    {
        if(col[e]==0)
        {
            col[e]=col[nod];
            dfs(e);
        }
    }
}



int main()
{
    cin>>n>>m;
    mst.resize(n+1);
    col.resize(n+1);
    min_ed.resize(n+1);
    
    for(int i=1;i<=m;i++)
    {
        cin>>ed[i].a>>ed[i].b>>ed[i].c;
    }
    ed[0].c=MV;
    
    set<int>sol;
    int ans=0;
    
    for(int b=0;b<50;b++)
    {
        for(int i=1;i<=n;i++) col[i]=0;
        int k=0;
        for(int i=1;i<=n;i++)
        {
            if(col[i]==0)
            {
                col[i]=++k;
                //cerr<<"HERE "<<i<<' '<<col[i]<<'\n';
                dfs(i);
            }
        }
        if(k==1) break;
        for(int i=1;i<=k;i++) min_ed[i]=0;
        for(int i=1;i<=m;i++)
        {
            if(col[ed[i].a]==col[ed[i].b]) continue;
            
            int a=ed[i].a,b=ed[i].b;
            
            for(int dir=0;dir<2;dir++)
            {
                swap(a,b);
                if(ed[min_ed[col[a]]].c>ed[i].c) min_ed[col[a]] = i;
            }
        }
        
        for(int i=1;i<=k;i++)
        {
            if(min_ed[i]==0) continue;
            if(sol.count(min_ed[i])>0) continue;
            
            int a=ed[min_ed[i]].a,b=ed[min_ed[i]].b;
            sol.insert(min_ed[i]);
            mst[a].push_back(b);
            mst[b].push_back(a);
            
            ans+=ed[min_ed[i]].c;
        }
    }
    
    //cout<<"HERE\n";
    cout<<ans<<'\n';
    cout<<sol.size()<<'\n';
    for(auto e:sol)
    {
        cout<<ed[e].a<<' '<<ed[e].b<<'\n';
    }
    
    return 0;
}