#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x,y;
};
int viz[200001],c[200001],dad[200001];
typedef pair<int, int> iPair;
priority_queue <iPair, vector <iPair>, greater<iPair> > Q;
vector <pair<int, int> > adj[200001];
vector <muchie> Sol;
int n,m,s=0;
void citire()
{
    int x,y,b;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>b;
        adj[x].push_back(make_pair(y, b));
        adj[y].push_back(make_pair(x, b));
    }

}
void afish()
{
    fout<<s<<"\n"<<n-1<<"\n";
    for(auto&v:Sol)
    {
        fout<<v.x<<" "<<v.y<<"\n";
    }
}

void Prim()
{
    for(int i=1; i<=n; i++)
    {
        c[i]=INT_MAX;
        Q.push(make_pair(c[i],i));
        viz[i]=1;
    }
    c[1]=0;
    dad[1]=0;
    viz[1]=0;
    Q.push(make_pair(0,1));

    while(!Q.empty())
    {
        int u=Q.top().second;
        Q.pop();
        viz[u]=0;
        for(auto&x:adj[u])
        {
            int v = x.first;
            int weight = x.second;
            if (viz[v] ==1 && c[v] > weight)
            {
                c[v] = weight;
                Q.push(make_pair(c[v], v));
                dad[v] = u;
            }
        }
    }
    for(int i=2; i<=n; i++)
    {
        s+=c[i];
        muchie a;
        a.x=i;
        a.y=dad[i];
        Sol.push_back(a);

    }
}


int main()
{
    citire();
    Prim();
    afish();
    return 0;
}