#include <bits/stdc++.h>
using namespace std;
	
#define FIN "apm.in"
#define FOUT "apm.out"
#define in f
#define out g
#define MAXSIZE 200002

ifstream f(FIN);
ofstream g(FOUT);
	
vector< pair< int,pair<int,int> > > s;
int father[MAXSIZE];

vector<pair<int,int> > tree;

	
int n,m,nr;
int minValue;
	

int find(int x)
{
    if(father[x] == x)
        return x;
    else return find(father[x]);
}
	
void uniune(int a, int b)
{
	int aRoot = find(a);
    int bRoot = find(b);
	
    if(aRoot == bRoot)
        return;
	
    if (rand() % 2 == 0) {
        father[aRoot] = bRoot;
    } else {
        father[bRoot] = aRoot;
    }
	
	
}
int read()
{
    in >> n;
    in >> m;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
	    in >> x;
	    in >> y;
	    in >> z;
        s.push_back(make_pair(z, make_pair(x,y)));
    }
}
int main()
{
    read();
    
	
    for(int i=1;i<=n;i++)
    {
        father[i] = i;
    }
    
    sort(s.begin(), s.end());
    
    
    
    int index = 0;
    while(nr < n-1)
    {
        int cost = s[index].first;
        int x = s[index].second.first;
        int y = s[index].second.second;
        if(find(x) != find(y))
        {
            uniune(x,y);
            minValue +=  cost;
            nr++;
            tree.push_back(make_pair(x,y));
        }
        index++;
    }
    out << minValue << '\n' << nr << '\n';
    
    for(int i=0;i<nr;i++)
    {
        out << tree[i].first << ' ' << tree[i].second << '\n';
    }
    return 0;
}