/// PRIM
#include <fstream>
#include <vector>
using namespace std;

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

const long long nmax = 3000;
const long long INF = 1e17 + 7;
long long a[2000][2000], inside[nmax], dist[nmax];
long long pr[nmax];
vector<pair<long long,long long>>ans;

long long main()
{
    long long n,m,i,j,s = 0;
    cin >> n >> m;
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            a[i][j] = INF;
    for(i=1;i<=m;i++)
    {
        long long u,v,w;
        cin >> u >> v >> w;
        a[u][v] = w;
        a[v][u] = w;
    }
    for(i = 1; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    pr[1] = 1;
    for(long long rep = 1; rep <= 2 * n; rep++)
    {
        long long dmin = 1e9, node = 0;
        for(i = 1; i <= n; i++)
        {
            if(inside[i] == 0 && dist[i] < dmin)
            {
                node = i;
                dmin = dist[i];
            }
        }
        inside[node] = 1;
        s += dist[node];
        if(node > 1)
            ans.push_back({node, pr[node]});
        for(i = 1; i <= n; i++)
        {
            if(inside[i] == 0 && a[node][i] < dist[i])
            {
                pr[i] = node;
                dist[i] = min(dist[i], a[node][i]);
            }
        }
    }
    cout << s << endl;
    cout << ans.size() << endl;
    for(auto it:ans)
        cout << it.first << " " << it.second << endl;
    return 0;
}