//prim
#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchii{
    int node, cost;
};

struct legaturi{
    int node, cost, tata;
};

struct compare{
    bool operator()(legaturi x, legaturi y){
        return x.cost > y.cost;
    }
};

int n,m,ok[200200],tata[200200],s;
vector <muchii> edges[200200];
priority_queue <legaturi, vector<legaturi>, compare> pq;

void prim(int x)
{
    pq.push({x,0,0});
    while(!pq.empty())
    {
        legaturi x = pq.top();
        pq.pop();
        if(ok[x.node]==0)
        {
            ok[x.node]=1;
            s += x.cost;
            tata[x.node]=x.tata;
            for(auto y:edges[x.node])
            {
                if(ok[y.node]==0)
                    pq.push({y.node, y.cost, x.node});
            }
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        edges[x].push_back({y,z});
        edges[y].push_back({x,z});
    }
    prim(1);
    g<<s<<'\n'<<n-1<<'\n';
    for(int i=2; i<=n; i++)
        g<<i<<' '<<tata[i]<<'\n';
    return 0;
}