#include <fstream>
#include <vector>
#include <queue>
#define N 200001
#define INF 1e6

using namespace std;

vector<pair<int,int>> graph[N];
priority_queue<pair<int,int>> h;
bool in_sol[N];
int pred[N];
int d[N];

int n,m,ans;

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

int primm()
{
    for(int i=2;i<=n;i++)
    {
        d[i]=INF;
    }
    h.push({0,1});
    while(!h.empty())
    {
        int x=h.top().second;
        h.pop();
        if(in_sol[x]) continue;
        in_sol[x]=1;
        ans+=d[x];
        for(auto p: graph[x])
        {
            int y=p.first,c=p.second;
            if(in_sol[y]) continue;
            if(c < d[y])
            {
                d[y]=c;
                pred[y]=x;
                h.push({-c,y});
            }
        }
    }
    return ans;
}

int main()
{
    in >> n >> m;
    for(int i=0;i<=m;i++)
    {
        int x,y,c;
        in >> x >> y >> c;
        graph[x].push_back({y,c});
        graph[y].push_back({x,c});
    }
    out << primm() << "\n" << n-1 << "\n";
    for(int i=2;i<=n;i++)
    {
        out << pred[i] << " " << i << "\n";
    }
    return 0;
}