#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

const int INF = 1 << 30;
const int MAX_N = 200100;
const int MAX_M = 400100;

vector<pair<int, int> > graph[MAX_N];
int n,m,t[MAX_N];
int cost[MAX_N], s[MAX_N];
int minim=0;

inline int da_cost(int a, int b)
{
    int i;
    int result = INF;
    for (auto x: graph[a]) {
        if (x.first == b) result = min(result, x.second);
    }
    return result;
}
void APM()
{
    int i,k,j,mini,ns,cn;
    ns=1;
    for(i=2;i<=n;i++) {
        cost[i]=da_cost(ns, i);
        s[i] = 1;
    }
    cost[ns]=0;
    s[ns] = 0;

    for(k=2;k<=n;k++)
    {
        mini=INF;
        for(i=2;i<=n;i++)
            if(s[i])
            {
                if (cost[i] == INF) continue;
                if(cost[i]<mini)
                {
                    mini=cost[i];
                    j=i;
                }
            }

        t[j]=s[j];
        minim=minim+mini;
        s[j]=0;
        for(i=2;i<=n;i++)
            if(s[i])
            {
                cn=da_cost(i,j);
                if(cn < cost[i]) {
                    cost[i] = cn;
                    s[i]=j;
                }
            }
    }
}
int main()
{
    int a,b,c,i,j;
    in>>n>>m;
    for(i=0;i<m;i++)
    {
        in>>a>>b>>c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    APM();
    out<<minim<<"\n";
    out<<n-1<<"\n";
    for(i=2;i<=n;i++)
        out<<t[i]<<" "<<i<<"\n";
    return 0;
}