// Template v2
#define pb push_back
#define mp make_pair
#define first x
#define second y
#define l(x) x<<1
#define r(x) x<<1 | 1
#define lsb(x) x & -x
#include<fstream>
#include<vector>
#include<algorithm>
#include <bitset>
using namespace std;
  
typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PKK;
// primes less than 100
const int PRIM[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
const int CMAX = 10005;
const int MOD = 700001;
const int NMAX = 400069;
const short INF16 = 32000;
const int INF = 2*1e9 + 6661369;
const LL INF64 = LL(1e18);
const LD EPS = 1e-9, PI = acos(-1.0);
const int dx[]={-1,1,0,0};
const int dy[]={0,0,1,-1};

ifstream cin("apm.in");
ofstream cout("apm.out");

struct edge{
    int x,y,c;
};

bool cmp(edge l, edge r)
{
    return l.c<r.c;
}

int p[NMAX/2], rang[NMAX/2];
edge E[NMAX];
int rs[NMAX];
int k, totsum, n,m;

int find(int x)
{
    int r, aux;
    for(r=x; r!=p[r]; r=p[r]);
    while(x!=r)
    {
        aux=p[x];
        p[x]=r;
        x=aux;
    }
    return r;
}

void unite(int x, int y)
{
    x=find(x); y=find(y);
    if(x!=y)
        p[x]=y;
}

void read()
{
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
        cin>>E[i].x>>E[i].y>>E[i].c;
    sort(E+1, E+1+m, cmp);
    
    for(int i=1; i<=n; ++i)
        p[i]=i;
    
    for(int i=1; i<=m; ++i)
    {
        if(find(E[i].x)!=find(E[i].y))
        {
            totsum+=E[i].c;
            unite(E[i].x, E[i].y);
            rs[++k]=i;
        }
    }
    
    cout<<totsum<<"\n";
    cout<<k<<"\n";
    for(int i=1; i<=k; ++i)
        cout<<E[rs[i]].x<<" "<<E[rs[i]].y<<"\n";
}
 
int main(){
    read();
      
    return 0;
}