#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <fstream>
#include <cstdlib>
#include <map>
#define pb push_back
#define mp make_pair
#define INF numeric_limits<int>::max()
#define bit(x) (-x)&x
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
pair< int , pair<int,int> > edge[400002];
#define cost first
#define x second.first
#define y second.second
vector<int> c;
vector<bool> use;
int n,m,tcost;
int group(int i)
{
    if(i==c[i])return i;
    c[i]=group(c[i]);
    return c[i];
}
void unite(int i,int j)
{
    c[group(i)]=group(j);
}
void Kruskal()
{
    for(int i=1;i<=n;i++)
        c[i]=i;
    for(int i=1,step=0;i<=m && step!=n-1;i++)
    if(group(edge[i].x) != group(edge[i].y))
    {
        unite(edge[i].x,edge[i].y);
        tcost+=edge[i].cost;
        step++;
        use[i]=true;
    }
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
        in>>edge[i].x>>edge[i].y>>edge[i].cost;
    c=vector<int> (n+1);
    use=vector<bool> (m+1);
    sort(edge+1,edge+m+1);
    Kruskal();
    out<<tcost<<'\n'<<n-1<<'\n';
    for(int i=1;i<=m;i++)
        if(use[i]==true)
        out<<edge[i].x<<' '<<edge[i].y<<'\n';
    return 0;
}