///Problema clasica

#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;

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

const int N=2e5;
const int INF=139;

struct vecin
{
    int vf;
    int cost;
};

int n, total;
vector<vecin> a[N+1];
vector<int> pred;

void prim()
{
    pred.resize(n+1);
    vector<int> d(n+1);
    d[0]=0;
    for(int i=2; i<=n; i++)
    {
        d[i]=INF;
    }
    priority_queue<pair<int, int>> h;
    bitset<N+1> selectat;
    h.push({0, 1});
    while(!h.empty())
    {
            int x = h.top().second;
            h.pop();
            if(selectat[x])
            {
                continue;
            }
            selectat[x]=true;
            total += d[x];
            for(auto v: a[x])
            {
                int y=v.vf, c=v.cost;
                if(!selectat[y] && c < d[y])
                {
                    d[y] = c;
                    pred[y] = x;
                    h.push({-c, y});
                }
            }
    }
}

int main()
{
    int m;
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        a[x].push_back((vecin){y, c});
        a[y].push_back((vecin){x, c});
    }
    prim();
    cout << total << '\n' << n-1 << '\n';
    for(int i=1; i<=n; i++)
        cout << pred[i] << " " << i << '\n';
    return 0;
}